Codeforces #230 Div1 B. Tower of Hanoi

本番これは割とすんなり解けてよかった。
http://codeforces.com/contest/392/problem/B

問題

ハノイの塔の問題を考える。
ただし、i番目の棒からj番目の棒に円盤を移すコストは一定ではなく、行列Tで与えられる。
1番の棒に刺さったN枚の円盤を3番の棒に移す最小コストを答えよ。

解法

メモ付再帰で解くことができる。
状態としては(動かす枚数,移動元棒番号,移動先棒番号)で与えられ、そのコストを最小化していく。
答えはもちろん(N,1,3)のコストである。

移動手順は以下の2つが考えられるので、コストの小さい方を取ればよい。
p番からq番に移動するとき、残りの棒をr番とすると：

• 上(N-1)枚をrに動かし、N枚目をqに動かし、上(N-1)枚をrからqに動かす。
• 上(N-1)枚をqに動かし、N枚目をrに動かし、上(N-1)枚をqからpに動かし、N枚目をrからqに動かし、上(N-1)枚をpからqに移動する。

普通のハノイの塔は上の手順だけを取るが、今回は移動コストが不均一なので後者の方が有効なケースがある。

int T[3][3],N;
ll dpdp[41][3][3];

ll calc(int n,int s,int e) {
	int t=3-s-e;
	if(n==1) return min(T[s][e],T[s][t]+T[t][e]);
	if(dpdp[n][s][e]==-1) {
		int t=3-s-e;
		dpdp[n][s][e] = min(calc(n-1,s,t) + T[s][e] + calc(n-1,t,e),calc(n-1,s,e)+T[s][t]+calc(n-1,e,s)+T[t][e]+calc(n-1,s,e));
	}
	return dpdp[n][s][e];
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>T[0][0]>>T[0][1]>>T[0][2];
	cin>>T[1][0]>>T[1][1]>>T[1][2];
	cin>>T[2][0]>>T[2][1]>>T[2][2];
	cin>>N;
	
	FOR(i,N+1) FOR(x,3) FOR(y,3) dpdp[i][x][y]=-1;
	cout << min(calc(N,0,2),calc(N,0,1)+calc(N,1,2)) << endl;
	
}

まとめ

これはすんなり解けてよかった。