【题目链接】: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;

}