View Code of Problem 1006

#include <cstdio>
#include <stack>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 70;
const unsigned long long INF=0xffffffffffffffff;///定义无限大
unsigned long long f[maxn][maxn]; ///f[i][j]表示i个盘，通过j个柱子，全程移动所需要的最少次数。
int pre[maxn][maxn]; ///pre[i][j]表示f[i][j]的最优方案是先将最小的path[i][j]个盘移动到中间某根的柱子上
int n,m;///n个盘子 m个柱子
stack<int>stk[maxn];
bool used[maxn];
void init()
{
   memset(f,INF,sizeof(f));
   for(int i=3;i<=65;i++)
   {
       f[0][i]=0;
       f[1][i]=1;
   }
   for(int i=1;i<=64;i++)
   {
       f[i][3]=2*f[i-1][3]+1;
       pre[i][3]=i-1;
   }
   for(int i=2;i<=64;i++)
    for(int j=4;j<=65;j++)
     for(int k=1;k<i;k++)
     {
       if(f[i][j]>2*f[k][j]+f[i-k][j-1])
       {
           f[i][j]=2*f[k][j]+f[i-k][j-1];
           pre[i][j]=k;
       }
    }
}
void dfs(int nt,int mt,int scr,int des)
{
   if(nt==1)
   {
       if(stk[des].size())
         printf("move %d from %d to %d atop %d\n",stk[scr].top(),scr,des,stk[des].top());
       else
         printf("move %d from %d to %d\n",stk[scr].top(),scr,des);
       stk[des].push(stk[scr].top());
       stk[scr].pop();
       return;
   }
   int peg=0;
   for(int i=1;i<=m;i++)
   {
       if(scr!=i && des!=i && !used[i])
       {
           peg=i;
           break;
       }
   }
   dfs(pre[nt][mt],mt,scr,peg);
   used[peg]=true;
   dfs(nt-pre[nt][mt],mt-1,scr,des);
   used[peg]=false;
   dfs(pre[nt][mt],mt,peg,des);
}
int main()
{
   init();
   int N;
   cin>>N;
   while(N--)
   {
       cin>>n>>m;
       for(int i=1;i<=m;i++) while(!stk[i].empty()) stk[i].pop();
       for(int i=n;i>=1;i--) stk[1].push(i);
       memset(used,false,sizeof(used));
       printf("%llu\n",f[n][m]);
       dfs(n,m,1,m);
   }
   return 0;
}