[SHOI2008]汉诺塔
ztx
posted @ 2015年1月13日 19:21
in 递推与递归
, 406 阅读
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | /****************************************\* Author : ztx* Title : [SHOI2008]汉诺塔* ALG : 递推* CMT :先解决子问题,把 x 柱上的 i-1 个圆盘移走,再把第 i 个大圆盘移走.设y = to[x][i-1] , z = 0+1+2-y-x (即除 x , y 以外的柱子编号)即 1)x 上 i-1 个圆盘移至 y 上 2)将 x 上的第 i 个圆盘移至z这时: 若 f[y][i-1] = z : 3)直接移到z结束 此情况: f[x][i] = f[x][i-1]+1+f[y][i-1] , to[x][i] = z 若 f[y][i-1] = x : 3)i-1 个圆盘移至 x 4)将 z 上的第 i 个圆盘移至 y 5)x 上 i-1 个圆盘移至y结束 此情况: f[x][i] = f[x][i-1]+1+f[y][i-1]+1+f[x][i-1] , to[x][i] = y* Time :\****************************************/ |
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 65 66 67 | /****************************************\* Author : ztx* Title : [SHOI2008]汉诺塔* ALG : 递推* CMT :先解决子问题,把 x 柱上的 i-1 个圆盘移走,再把第 i 个大圆盘移走.设y = to[x][i-1] , z = 0+1+2-y-x (即除 x , y 以外的柱子编号)即 1)x 上 i-1 个圆盘移至 y 上 2)将 x 上的第 i 个圆盘移至z这时: 若 f[y][i-1] = z : 3)直接移到z结束 此情况: f[x][i] = f[x][i-1]+1+f[y][i-1] , to[x][i] = z 若 f[y][i-1] = x : 3)i-1 个圆盘移至 x 4)将 z 上的第 i 个圆盘移至 y 5)x 上 i-1 个圆盘移至y结束 此情况: f[x][i] = f[x][i-1]+1+f[y][i-1]+1+f[x][i-1] , to[x][i] = y* Time :\****************************************/#include <cstdio>#define maxn 50LLtypedef long long ll ;int n ;int ope[10][2] = {0} ;ll f[4][maxn] = {0} ;int to[4][maxn] = {0} ;int i , CH , x , y , z ;int main() {// #define READ #ifdef READ freopen(".in" ,"r",stdin ) ; freopen(".out","w",stdout) ; #endif scanf("%d", &n ) ; for (i = 0 ; i < 6 ; i ++ ) { while (CH=getchar() , CH<'!') ; ope[i][0] = CH-'A' ; ope[i][1] = getchar()-'A' ; } for (x = 0 ; x < 3 ; x ++ ) for (i = 0 ; i < 6 ; i ++ ) if (ope[i][0] == x) { f[x][1] = 1 ; to[x][1] = ope[i][1] ; break ; } for (i = 2 ; i <= n ; i ++ ) for (x = 0 ; x < 3 ; x ++ ) { y = to[x][i-1] ; z = 3-x-y ; if (to[y][i-1] == z) to[x][i] = z , f[x][i] = f[x][i-1]+1+f[y][i-1] ; else to[x][i] = y , f[x][i] = f[x][i-1]+1+f[y][i-1]+1+f[x][i-1] ; } printf("%lld\n", f[0][n] ) ; #ifdef READ fclose(stdin) ; fclose(stdout) ; #else getchar() ; getchar() ; #endif return 0 ;} |
评论 (0)