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[3][3];

long long dp[3][3][45];

int main()
{
    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
            scanf("%d",&matrix[i][j]);
    int n;
    long long a,b;
    scanf("%d",&n);
    for(int k=1; k<=n; k++)
    {
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++)
            {
                if(i!=j)
                {
                    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);
                }
            }
    }
    cout<<dp[0][2][n]<<endl;;
}