ztx's Blog

/****************************************\
* 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   :
\****************************************/

/****************************************\
* 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  50LL

typedef 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 ;
}