程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva 10795 - A Different Task （遞歸+狀態轉移）

uva 10795 - A Different Task （遞歸+狀態轉移）

編輯：C++入門知識

題目鏈接：uva 10795 - A Different Task

思路來源於：點擊打開鏈接

題意：

新漢若塔問題，有n個盤子，放在3個盤子上，給你一個初始狀態和一個結束狀態，問你最小步數怎樣到達。

思路：

遞歸+狀態轉移，直接從初態到末態好像不是那麼好辦，對最大的一塊n，首先肯定要把他放在末態的位置上，假設開始在1號位置，要放到3號位置，那麼必須先到達這個狀態s：1~n-1必須都從大到小放在2上面，然後放n，然後將1~n-1轉移到末態，由對稱性，也即可以變為末態轉移到狀態s，那麼處理起來就可以統一了。

現在要解決怎樣將一個狀態轉移到s（1~k全部放到一個盤子c上面），要放k，那麼必須先有一個相似的狀態s0,：1~k-1放到一個盤子，然後轉移k，然後將1~k-1再放到k上面（原始的漢若塔問題，步數為2^(1<<(k-1)) ），可以看出解決s0和解決s是一個問題，這就得到了狀態轉移方程了，可以遞歸了。

函數 f (P,i,c),表示已知個盤子的初始柱面編號數組為P，把1到i移動到盤子c的步數，

答案就是f(st,k-1,6-st[k]-ed[k])+f(ed,k-1,6-st[k]-ed[k])+1;

然後是狀態轉移：計算f(P,i,c),若p[i]=c，則f(P,i,c)=f(P,i-1,c);否則需要把前i-1個盤子挪到中轉盤去，將盤子i移到柱子c去，做後把前i-1個盤子從中轉盤移到柱子c。

代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#pragma comment (linker,"/STACK:102400000,102400000")
#define maxn 1005
#define MAXN 50005
#define mod 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
typedef long long ll;
using namespace std;

ll n,m,ans,cnt,tot,flag;
ll st[65],ed[65];

ll f(ll p[],ll k,ll to)
{
    if(k==0) return 0;
    if(p[k]==to) return f(p,k-1,to);
    else return f(p,k-1,6-to-p[k])+(1LL<<(k-1));
}
int main()
{
    ll i,j,t,test=0;
    while(scanf("%lld",&n),n)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%lld",&st[i]);
        }
        for(i=1;i<=n;i++)
        {
            scanf("%lld",&ed[i]);
        }
        t=n;
        while(t>0&&st[t]==ed[t]) t--;
        if(t) ans=f(st,t-1,6-st[t]-ed[t])+f(ed,t-1,6-st[t]-ed[t])+1;
        else ans=0;
        printf("Case %lld: %lld\n",++test,ans);
    }
    return 0;
}