zoj 2338

HanioTower Edition
f[n][m]가 n개disc, m개peg인 Hanoi문제를 기록하면 dp공식 f[n][m]=min{f[n-k][m-1]+2*f[k][m]}가 있다.즉, 위의 k개disc를 m개peg으로 중간peg을 옮기고 아래의 n-k개disc를 m-1개peg으로 목표peg으로 옮기고 마지막으로 위의 k개disc를 m개peg으로 목표peg로 옮긴다.p프로세스는 f[n][m]의 최소 g[n][m]=k를 역방향 인쇄 이동 프로세스에 사용하도록 기록합니다.
 

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include <stack>

using namespace std;

typedef unsigned long long ll;

const ll INF=(~(0ULL))>>1;

ll dp[70][70];

int pre[70][70];

stack<int>v[80];

int n,m;

bool was[80];



void move(int from,int to) // a      b    

{

    if(v[to].empty()) printf("move %d from %d to %d
",v[from].top(),from,to);

    else printf("move %d from %d to %d atop %d
",v[from].top(),from,to,v[to].top());

    v[to].push(v[from].top());

    v[from].pop();

    return ;

}



void dfs(int ct,int from,int to,int h) //ct        a,b         h         

{

    int i,j,k;

    if(ct==1)

    {

        move(from,to);

        return ;

    }

    for(i=1;i<=m;i++)

        if(i!=from && i!=to && was[i]==0)break;

    dfs(pre[ct][h],from,i,h);

    was[i]=1;

    dfs(ct-pre[ct][h],from,to,h-1);

    was[i]=0;

    dfs(pre[ct][h],i,to,h);

}

void init(){

    int i,j,k;

    for(i=1;i<=70;i++) dp[i][3]=2*dp[i-1][3]+1,pre[i][3]=i-1;

    for(i=4;i<=65;i++){   //  

        dp[1][i]=1;

        for(j=2;j<=64;j++){  //  

            ll tem=INF;

            for(k=1;k<j;k++){ //   k          ，  j-k       ;

                if(tem > dp[j-k][i-1]+dp[k][i]*2){

                    tem=dp[j-k][i-1]+dp[k][i]*2;

                    pre[j][i]=k;

                }

            }

            dp[j][i]=tem;

        }

    }

}

int main()

{

    int i,j,k,ca,kk;



    init();

    scanf("%d",&ca);

    while(ca--)

    {

        scanf("%d%d",&n,&m);

        printf("%lld
",dp[n][m]);

        for(i=1;i<=m;i++)while(!v[i].empty())v[i].pop();

        for(i=n;i>=1;i--) v[1].push(i);

        memset(was,0,sizeof(was));

        dfs(n,1,m,m);

    }

    return 0;

}

 
f[n][m]가 n개disc, m개peg인 Hanoi문제를 기록하면 dp공식 f[n][m]=min{f[n-k][m-1]+2*f[k][m]}가 있다.즉, 위의 k개disc를 m개peg으로 중간peg을 옮기고 아래의 n-k개disc를 m-1개peg으로 목표peg으로 옮기고 마지막으로 위의 k개disc를 m개peg으로 목표peg로 옮긴다.p프로세스는 f[n][m]의 최소 g[n][m]=k를 역방향 인쇄 이동 프로세스에 사용하도록 기록합니다.