poj 1920 汉诺塔变种

思维题 链接

暂时没明白为啥好多poj的总结把它放在dp里

题目大意：现有汉诺塔残局，也就是说盘子零散地插在三个钉子上，当然各自也都遵守“上小下大”的摆放规律。求将其全部整理至一个钉子上所需最少步数，输出最后所在钉子位置（1，2，3）以及最小步数。

首先对于基础的汉诺塔问题，由数列递推式可得，将高度为n的塔从一个钉子上转移到另外一个钉子上所需步数为（2^n-1）

对于本题目，可逆向考虑，即求将一个整理好的塔分散至开局情况，所需最小步数。两者是一致的。

算法大致为，从下至上询问目的位置，在当前位则不需要移动，不在当前位则将其上（i-1）个移动至另一个位置，再将该盘子（i）移至目的地，花费（2^(i-1)）步数。

#include<iostream>
#include<cstdio>
using namespace std;

const int mod=1000000;
int pos[100000+4],num[3];
int s[100000+4];
int n;

int main()
{
    s[0]=1;
    for(int i=1;i<=100000;i++)
        s[i]=(s[i-1]*2)%mod;
    while(cin>>n)
    {
        for(int i=0; i<3; i++)
            scanf("%d",num+i);
        for(int i=1; i<=3; i++)
            for(int j=0; j<num[i-1]; j++)
            {
                int a;
                scanf("%d",&a);
                pos[a]=i;
            }
        int now=pos[n];
        int next=pos[n-1];
        int ans=0;
        for(int i=n-1;i>0;next=pos[--i]){
            if(now!=next){
                ans=(ans+s[i-1])%mod;
                now=6-now-next;
            }
        }
        cout<<pos[n]<<endl<<ans<<endl;
    }
    return 0;
}