Codeforce 392B Tower of Hanoi 区间dp

题目链接：http://codeforces.com/contest/393/problem/D

给定一个3*3的矩阵 [i,j] 表示把一个盘子从第i根柱子移到第j跟柱子的花费

下面一行n表示一共有n个盘子在1号柱子

问：全部都移动到3号柱子的最小花费

思路：

显然是一个区间dp

dp[num][i][j] 表示把num个盘子从 i->j 需要的最小花费

注意dfs是表示在上方的盘子移动的最小花费

在底部的那个盘子移动是 矩阵的花费

inf一定要足够大 1e18

#include<stdio.h>
#include<queue>
#include<iostream>
#include<string.h>
#include<math.h>
#include<set>
using namespace std;
#define inf 1000000000000000000
#define ll __int64
ll n;
ll map[3][3];
ll dp[42][3][3];
ll dfs(ll num, ll s, ll t){
	if(dp[num][s][t]<inf)return dp[num][s][t];
	ll ans = inf, i;
	ll z = 6/((1+s)*(1+t))-1;
	ll sz = min(dfs(num-1,s,z), dfs(num-1,s,t)+dfs(num-1,t,z));//s-z
	ll zt = min(dfs(num-1,z,t), dfs(num-1,z,s)+dfs(num-1,s,t));//z-t
	ll st = min(dfs(num-1,s,t), dfs(num-1,s,z)+dfs(num-1,z,t));//s-t
	ll ts = min(dfs(num-1,t,s), dfs(num-1,t,z)+dfs(num-1,z,s));//t-s

	ans = min(ans, map[s][t]+sz+zt);
	ans = min(ans, st+map[s][z]+ts+map[z][t]+st);
	return dp[num][s][t] = ans;
}
int main()
{
	ll i,j,n;

	while(~scanf("%I64d",&map[0][0]))
	{
		scanf("%I64d %I64d",&map[0][1],&map[0][2]);
		for(i=1;i<=2;i++)for(j=0;j<=2;j++)scanf("%I64d",&map[i][j]);
		scanf("%I64d",&n);
		for(i=2;i<=n;i++)	for(j=0;j<3;j++)	for(ll k = 0; k < 3; k++)	dp[i][j][k] = inf;

		memset(dp[0], 0, sizeof(dp[0]));
		for(i=0;i<=2;i++)for(j=0;j<=2;j++)
			dp[1][i][j] = min(map[i][j],map[i][6/((1+i)*(1+j))-1]+map[6/((1+i)*(1+j))-1][j]);

		for(i=1;i<=n;i++)	for(j=0;j<3;j++)	dp[i][j][j] = 0;
		printf("%I64d\n", dfs(n,0,2));
	}
	return 0;
}
/*
0 1 1
1 0 1
1 1 0
3
0 2 2
1 0 100
1 2 0
3
0 2 1
1 0 100
1 2 0
5
0 1 10
1 0 1
10 1 0
1

*/

原文：http://blog.csdn.net/acmmmm/article/details/19572301