POJ3601_“TowerofHanoi”汉诺塔问题变型探讨.doc

汉诺塔变形POJ 3601 Tower of Hanoi 递推2008-07-31 12:16Tower of HanoiTime Limit:1000MSMemory Limit:131072KTotal Submissions:423Accepted:92DescriptionThe Tower of Hanoi is a puzzle consisting of three pegs and a number of disks of different sizes which can slide onto any peg. The puzzle starts with the disks neatly stacked in order of size on one peg, the smallest at the top, thus making a conical shape. The objective of the puzzle is to move the entire stack to another peg, obeying the following rules: Only one disk may be moved at a time. Each move consists of taking the upper disk from one of the pegs and sliding it onto another peg, on top of the other disks that may already be present on that peg. No disk may be placed on top of a smaller disk.Forndisks, it is a well-known result that the optimal solution takes 2n 1 moves.To complicate the puzzle a little, we allow multiple disks to be of the same size. Moreover, equisized disks are mutually distinguishable. Their ordering at the beginning should be preserved at the end, though it may be disturbed during the process of solving the puzzle.Given the number of disks of each size, compute the number of moves that the optimal solution takes.InputThe input contains multiple test cases. Each test case consists of two lines. The first line contains two integersnandm(1 n 100, 1 m 106). The second lines containsnintegersa1,a2, ,an(1 a1,a2, ,an 105). For each 1 in, there areaidisks of sizei. The input ends where EOF is met.OutputFor each test case, print the answer modulomon a separate line.Sample Input1 100025 10001 1 1 1 15 10002 2 2 2 25 10001 2 1 2 1Sample Output33112341题意：古老的汉诺塔问题，也是有由3个杆，但是叠的圆盘可能会有相同大小的，对于相同大小的圆盘，在最后移动完毕之后也必须保证按照原来的顺序排放，问移动的最少步数思路：考虑最原始的汉诺塔，也就是每种圆盘只有一个，那么用dpi表示对于i层得最少移动步数，有dpi=dpi-1*2+1，移动放法是移动前i-1个，再移动第i个，再移动前i-1个那么对于这道题，其实唯一不同的地方就是，对于一样大小的圆盘，如果直接移动到目的地，那么他们的标号就会变反（比如123-321），对于两种以上的圆盘，那么按照之前的移动方式，前i-1堆会是顺序排放的，最后一堆会变反，所以用dp1i表示直接移，也就是最后一堆是反的的最小步数，dp2i表示最后一堆也是正的最小步数，有状态转移方程：dp1i=dp1i-1*2+si，dp2的移动方式是前i-1堆移动（最后一堆现在是反的），移动第i堆（现在是反的），移动前i-1堆（最后一堆现在是正的），移动第i堆（现在是正的），按照正的方式移动前i-1堆，总的代价就是dp2i=dp1i-1*2+dp2i-1+2*si，注意要特别判断si=1的情况考虑用移位运算提高运算效率。1. #include2. #defineN1013. 4. intmain()5. 6. intdp1 N=0,/最下面一种盘反向7. dp2 N=0,/最下面一种盘正向8. sN,m,n;9. 10. while(scanf(%d%d,&n,&m)!=EOF)11. 12. inti,j;13. for(i=1;i=n;+i)14. scanf(%d,&si);15. dp1 1=s1%m;16. dp2 1=(2*s1-1)%m;17. for(i=2;i=n;+i)18. 19. dp1 i=(dp1 i-11)+si)%m;20. if(si