似乎这个汉诺塔可以写个dp

首先题意:

给你个n个盘子,m只柱子的汉诺塔

让你求个移动方案

链接:http://codeforces.com/gym/100197/attachments/download/1683/20032004-andrew-stankevich-contest-1-en.pdf

这一题其实做法不难,只要一个dp即可

dp(i,j) i个盘子j个柱子最优策略

我们可以考虑,把k个盘子搬到某个柱子上,然后用剩下j-1个柱子做dp(i-k,j-1),最后再搬回来,这么做实际上是可行的...

那么方程自然有了,转移以后再写个dfs求方案即可....

求方案的时候我就暴力了...

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[75][75];
int last[75][75];
int que[75][75];
int front[75];
int n,m;
void moves(int x,int y,int s,int t)
{
    if (x==1)
    {
        printf("move %d from %d to %d",que[s][front[s]-1],s,t);
        if (front[t]!=0) printf(" atop %d",que[t][front[t]-1]);
        printf("\n");
        que[t][front[t]]=que[s][front[s]-1];
        front[s]--;
        front[t]++;
        return;
    }
    int z;
    int val=que[s][front[s]-1];
    for (z=1;z<=m;z++)
    {
        if (z==t) continue;
        if (front[z]==0) break;
        if (que[z][front[z]-1]<=val) continue;
        break;
    }
    moves(last[x][y],y,s,z);
    moves(x-last[x][y],y-1,s,t);
    moves(last[x][y],y,z,t);
}
int main()
{
    freopen("hanoi.in","r",stdin);
    freopen("hanoi.out","w",stdout);
    scanf("%d%d",&n,&m);
    int i;
    for (i=1;i<=28;i++)
    {
        dp[i][3]=(1<<i)-1;
        last[i][3]=i-1;
    }
    for (i=1;i<=n;i++)
    {
        int j;
        for (j=4;j<=m;j++)
        {
            dp[i][j]=dp[i-1][j]*2+1;
            last[i][j]=i-1;
            int k;
            for (k=1;k<i;k++)
            {
                if ((j==4)&&(i-k>28)) continue;
                if (dp[i][j]>dp[k][j]*2+dp[i-k][j-1])
                {
                    dp[i][j]=dp[k][j]*2+dp[i-k][j-1];
                    last[i][j]=k;
                }
            }
        }
    }
    front[1]=n;
    for (i=1;i<=n;i++)
    {
        que[1][i-1]=n-i+1;
    }
    printf("%d\n",dp[n][m]);
    moves(n,m,1,m);
    return 0;
}