UOJ Logo chtomede的博客

博客

#61. 新新汉诺塔

2019-02-03 22:56:53 By chtomede

代码:

#include<iostream>
#include<cstring>
using namespace std;
int a[13],b[13];//a数组中存放三级汉诺塔步数,b数组即为答案
int main(){
    memset(b,0x3f,sizeof(b));
    b[1]=1;

    for(int i=1;i<=12;i++)
        a[i]=2*a[i-1]+1; 

    for(int i=1;i<=12;i++)
        for(int j=1;j<i;j++)
            b[i]=min(b[i],2*b[j]+a[i-j]); 

    for(int i=1;i<=12;i++)
        cout<<b[i]<<endl;

    return 0;
}

b需要DP(感觉很暴力,一点没有递推的感觉)求出:

    b[i]=min(b[i],2*b[j]+a[i-j]);

b[j]表示的是上层的j个盘子到达目的地的次数(此时有4个柱子参与)

a[i-j]为剩下i-j个盘子的次数(此时就只有3个柱子参与,前j个占了一个柱子)

由于把前j个得挪回去,所以要把b[j]乘2;

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。