Codeforces 392(#290 Div1) B. Tower of Hanoi

問題

ハノイの塔がある。
通常のルールに加えて、軸iにささっている円盤を軸jに移動するときにcost[i][j]がかかる。
最初軸0にささっているn枚の円盤を、軸2に全て移動させるのにかかるコストの最小値を求めよ。

制約条件

n≦40
0≦cost[i][j]≦10000

方針

DPするだけ。
rec(n, i, j) := n枚の円盤をiからjにうつすコスト
あまってる軸をkとする。

n-1枚をkにうつしてn枚目をjにうつしてn-1枚をjに移す or
n-1枚をjにうつしてn枚目をkにうつしてn-1枚をiに移して、n枚目をjにうつして、n-1枚をjに移す
のうちコストの小さいほうを取ればいい。

ソースコード

int n, t[3][3];
ll dp[51][3][3];

ll rec(int n, int a, int b){
	ll &res = dp[n][a][b];
	if(res >= 0) return res;
	
	int c = 0;
	rep(i, 3) if(i != a && i != b) c = i;
	
	if(n == 1) return res = min(t[a][b], t[a][c] + t[c][b]);
	
	ll cost1 = rec(n-1, a, c) + t[a][b] + rec(n-1, c, b);
	ll cost2 = rec(n-1, a, b) + t[a][c] + rec(n-1, b, a) + t[c][b] + rec(n-1, a, b);
	
	res = min(cost1, cost2);
	return res;
}
int main(){
	rep(i, 3) rep(j, 3) cin >> t[i][j];
	cin >> n;
	memset(dp, -1, sizeof(dp));
	cout << rec(n, 0, 2) << endl;
	return 0;
}