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;;
}
上一篇:所生成项目的处理器架构“MSIL”与引用“Microsoft.AspNet.Scaffolding.12.0, Version=12.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a, processorArchitecture=x86”的处理器架构“x86”不匹配。


下一篇:使用Canvas制作画图工具