【题目链接】:http://www.lydsy.com/JudgeOnline/PRoblem.php?id=1019
【题意】
【题解】 这个题解讲得很清楚了 http://blog.sina.com.cn/s/blog_76f6777d0101b8l1.html 大概就是设 f[i][j],g[i][j]分别表示第i个塔上有j个盘,然后这j个盘全部转移到g[i][j]上的方案数; f[1..3][1]和g[1..3][1]都能根据一开始那个东西确定. 第i个塔有n个盘 则n-1个移到一个上 然后剩一个大的放在另外一个上面; 然后再把它们合在一起就能整体移出去了 (对一个盘只能操作一次,不,应该说不能对一个盘连续操作,n-1个盘看成整体一个盘); 根据汉诺塔的移动规则写递推. 最后输出f[1][n] 我把分析摘录下来。 都是上面那个博客的.
/*f[x][i],g[x][i] 可由 f[][i-1],g[][i-1] 推得:汉诺塔的经典转移，先做子问题把x柱上的i-1个圆盘移走，再把第i个大圆盘移走..若设y=g[x][i-1],z=1+2+3-y-x（即除x,y以外的柱子编号）即1) x上i-1个圆盘移至y上 2)由于不能对一个圆盘进行重复操作，所以必是将x上的第i个圆盘，移至z 由于i个圆盘还没叠到一起，所以接下来显然还要再次移动y上的i-1个，这时需要分类讨论: 若 f[y][i-1]=z: 3)移到z后，便结束了 综合以上，这种情况下,f[x][i]=f[x][i-1]+1+f[y][i-1],g[x][i]=z 若f[y][i-1]=x: 3)i-1个圆盘移至x 4)不能对一个圆盘进行重复操作，所以必将z上的第i个圆盘，移至y 5)因g[x][i-1]=y，所以x上i-1个圆盘移至y，结束 综合以上，这种情况下，f[x][i]=f[x][i-1]+1+f[y][i-1]+1+f[x][i-1],g[x][i]=y */ps:这题还能构造线性关系搞 即 f[n] = k*f[n-1]+b; 求出k和b就能搞; 当然要从n>=3开始. 【完整代码】
#include <bits/stdc++.h>using namespace std;#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define LL long long#define rep1(i,a,b) for (int i = a;i <= b;i++)#define rep2(i,a,b) for (int i = a;i >= b;i--)#define mp make_pair#define pb push_back#define fi first#define se second#define rei(x) scanf("%d",&x)#define rel(x) scanf("%lld",&x)typedef pair<int, int> pii;typedef pair<LL, LL> pll;const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };const double pi = acos(-1.0);const int N = 40;int n;char s[8][5];LL f[4][N];int g[4][N];int main(){ //freopen("F://rush.txt", "r", stdin); rei(n); rep1(i, 1, 6) scanf("%s", s[i]); rep1(i, 1, 3) { rep1(j, 1, 6) { if (s[j][0] - 'A' + 1 == i) { g[i][1] = s[j][1] - 'A' + 1; f[i][1] = 1; break; } } } rep1(i, 2, n) { rep1(x, 1, 3) { int y = g[x][i - 1]; int z = 1 + 2 + 3 - x - y; if (g[y][i - 1] == z) { f[x][i] = f[x][i - 1] + 1 + f[y][i - 1]; g[x][i] = z; } else { f[x][i] = f[x][i - 1] + 1 + f[y][i - 1] + 1 + f[x][i - 1]; g[x][i] = y; } } } printf("%lld/n", f[1][n]); return 0;}新闻热点
疑难解答
