hdu 1207ハノータII四柱

タイトルリンクhttp://acm.hdu.edu.cn/showproblem.php?pid=1207

Problem Description
                       。                。               ，                ，                 64     。                               。    ，           ，                 。    ，                  。                      。 ，          ，                 。Gardon                 。 
　　Gardon       （ ，       ），    64                          ，  Gardon      ，              ，                        。       ： Gardon         N    ，                      ？   ，         ，     2^N-1，            ，      ？


Input
      ，      ，      N(1<=N<=64)。


Output
      ，     ，             。


Sample Input
1
3
12


Sample Output
1
5
81

问题描述:经典汉诺塔的基础上加一个条件,即使再加一本柱(即现在有四本柱a,b,c,d),计算将n个盘从第一本柱(a)全部转移到最后一本柱(d)上需要的最少步数,当然,也不能出现大的盆子放在小盆上.注:1<=n<=64;分析:设F[n]求めた最小ステップ数のために、明らかにn=1のとき、F[n]=1;n=2のとき、F[n]=3;古典的なハンノタワーのように、皿を移動したタスクを3つのステップに分けた:(1)x(1<=x<=n)個のディスクをaカラムからbに、dカラムからcカラムに、このプロセスに必要なステップ数はF[x];(2)aカラムに残ったn-x個のディスクをbカラムに依存してdカラムに移動する(注:この場合、c柱に頼ることはできない.c柱上のすべてのディスクがa柱上のディスクより小さいため)時間の移動方式は古典的なハンノタワーに相当する.すなわち、このプロセスに必要なステップ数は2^(n-x)-1(再議論ハンノタワー1を参照)である.(3)c柱上のx個のディスクをa,b柱に依存してd柱に移動する.このプロセスに必要なステップ数はF[x];第(3)ステップ終了後にタスクが完了する.したがって、タスクを完了するために必要な総ステップ数F[n]=F[x]+2^(n-x)-1+F[x]=2*F[x]+2^(n-x)-1であるが、これはまだ要求に達していない.問題で要求されているのは最小限のステップ数を求めることであり、上式が分かりやすく、xの異なる値を取るにつれて、同じnに対しても異なるF[n]が得られる.すなわち、実際にこの問題の答えはmin{2*F[x]+2^(n-x)+1}であるべきである1<=x<=nであり、xの各値をループで巡回し、xの各値のF[n]の最小値を1つのタグ変数minで記録することができる.数値は大きくなく、intは完全に解決できる.コードは以下の通りである.

#include <iostream>
#include <cmath>
using namespace std;
const int INF=9999999;

int f[65];
void init()
{
    f[1]=1;f[2]=3;
    for(int i=3;i<65;i++)
    {
        int min_x=INF;
        for(int x=1;x<i;x++)
        {
            if(2*f[x]+pow(2.0,i-x)-1<min_x)
            min_x=2*f[x]+pow(2.0,i-x)-1;
        }
//          ,   tmp   
// for(int x=1;x<i;x++)
// {
// int tmp=2*f[x]+pow(2.0,i-x)-1;
// if(tmp<min_x)
// min_x=tmp;
// }
        f[i]=min_x;
    }
}
int main()
{int n;
 init();
 while(cin>>n)
 {
     cout<<f[n]<<endl;
 }

    return 0;
}