codeforces 392B Tower of Hanoi

把前n个碟子从第一个塔移动到第三个塔有两种方法：

1.把前n-1个移动到第二个塔，把第n个移动到第三个塔，然后把前n-1个从第二个移动到第三个；

2.把前n-1个移动到第三个塔，把第n个移动到第二个塔，然后把前n-1个继续移动到第一个的塔，把第N个移动到第三个塔，最后把前n个移动到第三个塔就行了；

状态转移方程：

a=dp[i][3-i-j][k-1]+matrix[i][j]+dp[3-i-j][j][k-1];
b=dp[i][j][k-1]+matrix[i][3-i-j]+dp[j][i][k-1]+matrix[3-i-j][j]+dp[i][j][k-1];
dp[i][j][k]=min(a,b);

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

int matrix[][];

long long dp[][][];

int main()

{

    for(int i=; i<; i++)

        for(int j=; j<; j++)

            scanf("%d",&matrix[i][j]);

    int n;

    long long a,b;

    scanf("%d",&n);

    for(int k=; k<=n; k++)

    {

        for(int i=; i<; i++)

            for(int j=; j<; j++)

            {

                if(i!=j)

                {

                    a=dp[i][-i-j][k-]+matrix[i][j]+dp[-i-j][j][k-];

                    b=dp[i][j][k-]+matrix[i][-i-j]+dp[j][i][k-]+matrix[-i-j][j]+dp[i][j][k-];

                    dp[i][j][k]=min(a,b);

                }

            }

    }

    cout<<dp[][][n]<<endl;;

}

巴特西

codeforces 392B Tower of Hanoi

最新文章

热门文章