首页 > 代码库 > BZOJ1019 SHOI2008 汉诺塔 一般DP
BZOJ1019 SHOI2008 汉诺塔 一般DP
题意：给定汉诺塔移动的优先级（由大到小且两次操作不移动同一个盘子，则能执行的一定执行）和盘子的数量，求移动次数。
题解：设f[i][j]=将i柱子上j个盘子移动到满足要求的柱子上的步数，g[i][j]=移走i柱子上j个盘子按要求会移动到g[i][j]这个柱子。有两种转移的情况
（以下1 2 3仅作代表以方便叙述，不代表具体的柱子）
1、1柱子上移动i个盘子到3：需要先将i-1个盘子移动到2，再移动第i个盘子到3，再移动2上的i-1个盘子到3——f[1][i]=f[1][i-1]+1+f[2][i-1]
2、1柱子上移动i个盘子到2：需要先将i-1个盘子移动到2，在移动第i个盘子到3，再移动i-1个盘子到1，再移动第i个盘子到2，再移动i-1个盘子到2——f[1][i]=f[1][i-1]+1+f[2][i-1]+1+f[1][i-1]。
具体的1 2 3柱子由g数组决定。
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;#define ll long longconst int MAXC=3+2;const int MAXN=30+2;int N,x[MAXN],y[MAXN],g[MAXC][MAXN];ll f[MAXC][MAXN];char S[MAXC];int main(){ cin >> N; for(int i=1;i<=6;i++){ cin >> S; x[i]=S[0]-‘A‘+1,y[i]=S[1]-‘A‘+1; } f[1][1]=f[2][1]=f[3][1]=1; for(int i=6;i;i--) g[x[i]][1]=y[i]; for(int i=2;i<=N;i++) for(int a=1;a<=3;a++){ int b=g[a][i-1],c=6-a-b; if(g[b][i-1]==c) f[a][i]=f[a][i-1]+1+f[b][i-1],g[a][i]=c; else if(g[b][i-1]==a) f[a][i]=2*f[a][i-1]+2+f[b][i-1],g[a][i]=b; } cout << f[1][N] << endl; return 0;}
BZOJ1019 SHOI2008 汉诺塔 一般DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。