【进阶的汉诺塔】code forces 392B Tower of Hanoi

code forces   392B   Tower of Hanoi          题目链接：http://codeforces.com/problemset/problem/392/B

有了http://blog.csdn.net/blogs_of_slicer/article/details/20533637这一篇理解的基础，这道题就算已经完成了三分之一了。

题目大意：还是汉诺塔，不过这次每一步移动都有一定花费，求最小花费。

题目分析：经典汉诺塔的递归方法都是【把上n-1个环从起始柱经由目标柱移动到中间柱，把最下面的第n个直接移动到目标柱上，再将中间柱上的递归移到目标柱】。由于这道题引入了花费，要求最小花费就要考虑更多情况，除了上面一种情况，还可以【先把上n-1个环经由中间柱移动到目标柱，把第n个环直接移动到中间柱，再把目标柱上的n-1个环经由中间柱移回到起始柱，这时把中间柱上的最大环移动到目标柱，最后把起始柱上的n-1个环递归移到目标柱】，这两种情况各产生一个花费，取较小的那个存下来，由于是大量重复递归，所以用上记忆化搜索就再合适不过了。

code:

#include<iostream>
#include<cstring>
#define LL long long
using namespace std;
int cost[4][4];
LL dp[45][4][4][4];
LL hanoi(int n,int a,int b,int c)
{
    if(dp[n][a][b][c]!=-1)return dp[n][a][b][c];
    LL tmp1,tmp2;
    tmp1=hanoi(n-1,a,c,b)+cost[a][c]+hanoi(n-1,b,a,c);
    tmp2=hanoi(n-1,a,b,c)+cost[a][b]+hanoi(n-1,c,b,a)+cost[b][c]+hanoi(n-1,a,b,c);
    return dp[n][a][b][c]=tmp1>tmp2?tmp2:tmp1;
}
int main()
{
    int i,j,n;
    memset(dp,-1,sizeof(dp));
    memset(dp[0],0,sizeof(dp[0]));
    for(i=0;i<3;i++)
    {
        for(j=0;j<3;j++)
        {
            cin>>cost[i][j];
        }
    }
    cin>>n;
    cout<<hanoi(n,0,1,2)<<endl;
    return 0;
}

【进阶的汉诺塔】code forces 392B Tower of Hanoi,布布扣,bubuko.com

【进阶的汉诺塔】code forces 392B Tower of Hanoi

原文：http://blog.csdn.net/blogs_of_slicer/article/details/20652073