【題目鏈接】:http://www.lydsy.com/JudgeOnline/PRoblem.php?id=1019
【題意】
【題解】 這個(gè)題解講得很清楚了 http://blog.sina.com.cn/s/blog_76f6777d0101b8l1.html 大概就是設(shè) f[i][j],g[i][j]分別表示第i個(gè)塔上有j個(gè)盤,然后這j個(gè)盤全部轉(zhuǎn)移到g[i][j]上的方案數(shù); f[1..3][1]和g[1..3][1]都能根據(jù)一開始那個(gè)東西確定. 第i個(gè)塔有n個(gè)盤 則n-1個(gè)移到一個(gè)上 然后剩一個(gè)大的放在另外一個(gè)上面; 然后再把它們合在一起就能整體移出去了 (對一個(gè)盤只能操作一次,不,應(yīng)該說不能對一個(gè)盤連續(xù)操作,n-1個(gè)盤看成整體一個(gè)盤); 根據(jù)漢諾塔的移動規(guī)則寫遞推. 最后輸出f[1][n] 我把分析摘錄下來。 都是上面那個(gè)博客的.
/*f[x][i],g[x][i] 可由 f[][i-1],g[][i-1] 推得:漢諾塔的經(jīng)典轉(zhuǎn)移，先做子問題把x柱上的i-1個(gè)圓盤移走，再把第i個(gè)大圓盤移走..若設(shè)y=g[x][i-1],z=1+2+3-y-x（即除x,y以外的柱子編號）即1) x上i-1個(gè)圓盤移至y上 2)由于不能對一個(gè)圓盤進(jìn)行重復(fù)操作，所以必是將x上的第i個(gè)圓盤，移至z 由于i個(gè)圓盤還沒疊到一起，所以接下來顯然還要再次移動y上的i-1個(gè)，這時(shí)需要分類討論: 若 f[y][i-1]=z: 3)移到z后，便結(jié)束了 綜合以上，這種情況下,f[x][i]=f[x][i-1]+1+f[y][i-1],g[x][i]=z 若f[y][i-1]=x: 3)i-1個(gè)圓盤移至x 4)不能對一個(gè)圓盤進(jìn)行重復(fù)操作，所以必將z上的第i個(gè)圓盤，移至y 5)因g[x][i-1]=y，所以x上i-1個(gè)圓盤移至y，結(jié)束 綜合以上，這種情況下，f[x][i]=f[x][i-1]+1+f[y][i-1]+1+f[x][i-1],g[x][i]=y */ps:這題還能構(gòu)造線性關(guān)系搞 即 f[n] = k*f[n-1]+b; 求出k和b就能搞; 當(dāng)然要從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;}新聞熱點(diǎn)
疑難解答
