hdu-1207（规律推导）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1207

思路：

可以按照类似汉诺塔的推导形式来推导，

首先，有四个柱子，a，b，c，d。

（1）a的x个盘子借b，d转移到c上,要F（x）次；

（2）a的n-x个盘子借b转移到d上（就是普通的汉诺塔）要2^(n-x)-1次;

（3）c的x借a，b转移到d上需要F（x）次。

所以总共要2*F(x)+2^(n-x)-1次,所以将x从1--n-1遍历即可。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int INF = 99999999;
int a[120];
int main(void)
{
    int mi,n,i,j;
    a[0]=0;a[1]=1;a[2]=3;a[3]=5;
    for(i=4;i<=64;i++)
    {
        mi=INF;
        for(j=1;j<i;j++)
        mi=mi<(2*a[j]+pow(2,i-j)-1)?mi:(2*a[j]+pow(2,i-j)-1);
        a[i]=mi;
    }
    while(~scanf("%d",&n))
    {
        printf("%d
",a[n]);
    }
    return 0;
}