把前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;;
}