题意
可以参考LRJ大礼包白书第一章例题11
和汉诺塔游戏一样的规则,区别是这个问题会给出多达60个圆盘每一个最开始在哪根柱子上,要你求出从这个局势开始到终盘(00n)最少要移动多少次。
思路
大概是个。。。构造题?
思路比较复杂,而且还涉及传统汉诺塔问题的结论(把一根有k个盘子的堆移到一个空柱子上,需要((2^k)-1)步)。
具体的思路可以参考白书P27.
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> using namespace std; const int MAXN = 105; int init[MAXN]; int end[MAXN]; int n; int interchange(int a,int b){ return 6-a-b; } long long func(int *P,int i,int fin){ if(i == 0){ return 0; } if(P[i] == fin){ return func(P,i-1,fin); } return func(P,i-1,interchange(P[i],fin)) + (1LL << (i-1)); } long long solve(){ int k = n; for(; k >= 1; k--){ if(init[k] != end[k]){ break; } } if(!k) return k; return func(init,k-1,interchange(init[k],end[k])) + func(end,k-1,interchange(init[k],end[k])) + 1; } int main(){ int caseCnt = 0; while(scanf(" %d",&n) != EOF && n){ caseCnt++; for(int i = 1; i<= n;i++){ scanf(" %d",&init[i]); } for(int i = 1; i<= n; i++){ scanf(" %d",&end[i]); } printf("Case %d: %lld\n",caseCnt,solve()); } return 0; } |