大白_uva10795_新汉诺塔

题意：给出所有盘子的初态和终态，问最少多少步能从初态走到终态，其余规则和老汉诺塔一样。

思路：

若要把当前最大的盘子m从1移动到3，那么首先必须把剩下的所有盘子1~m-1放到2上，然后把m放到3上。

现在要解决怎样将一个状态s0转移到s（1~k全部放到一个盘子c上面），要放k，那么必须先有一个相似的状态s0,：1~k-1放到一个盘子，然后转移k，然后将1~k-1再放到k上面（原始的汉若塔问题，步数为2^(1<<(k-1)) ），可以看出解决s0和解决s是一个问题，这就得到了状态转移方程了，可以递归了。

由老汉诺塔的公式，将n个在一个柱子上排列好的盘子移动到另一个柱子需要2^n步。

#include<cstdio>

#include<set>

#include<iostream>

#include<vector>

#include<algorithm>

#include<map>

using namespace std;

#define N 65

int st[N];

int en[N];

long long solve(int *p,int x,int epos)

{

    if(x==)

        return ;

    if(p[x]==epos)

        return solve(p,x-,epos);

    return solve(p,x-,-epos-p[x])+(1LL<<(x-));

}

int main()

{

    int n,cnt=;

    while(scanf("%d",&n)!=EOF&&n)

    {

        for(int i=; i<=n; i++)

            scanf("%d",&st[i]);

        for(int i=; i<=n; i++)

            scanf("%d",&en[i]);

        int k=n;

        while(st[k]==en[k])

            k--;

        long long res=;

        if(k>)

        {

            int other=-st[k]-en[k];

            res=solve(st,k-,other)+solve(en,k-,other)+;

        }

        printf("Case %d: %lld\n",++cnt,res);

    }

    return ;

}

巴特西

大白_uva10795_新汉诺塔

最新文章

热门文章