Codeforces Round #230 (Div.1) B. Tower of Hanoi
問題概要
ハノイの塔のパズルの最小手数は 2^n - 1 であることは有名な事実であるが,今回は以下の問題を考えるとする.
ある段を位置 i から位置 j に移すのにコストが t[i][j] かかるとするとき( 1 <= i, j <= 3 ),最初位置 0 にある n 段の塔を,位置 2 に移すときのトータルのコストを最小化せよ.手数は最小化しなくともよい.
・制約
1 <= n <= 40
解法
最小手数が 2^n - 1 である,ということの漸化式の証明が頭にあれば,すぐに dp の式を導けると思います.
dp[i][from][to] := i 段の塔を位置 from から to に移すときの最小コスト
とします.また,もう一つの位置を other とします.
dp[i][from][to] は,以下の2つのどちらかです.
- i - 1 段の塔を from から other に移す.その後,i 段目を from から to に移す.最後に i - 1 段の塔を other から to に移す.
- i - 1 段の塔を from から to に移す.次に i 段目を other に移す.その後 i - 1 段の塔をまた from に戻す.そして i 段目を other から to に移す.最後に i - 1 段の塔を from から to に移す.
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { int t[3][3] = {}; int n; for(int i = 0; i < 3; ++i) { for(int j = 0; j < 3; ++j) { cin >> t[i][j]; } } cin >> n; ll dp[41][3][3] = {}; for(int i = 1; i <= n; ++i) { for(int from = 0; from < 3; ++from) { for(int to = 0; to < 3; ++to) { int other = 3 - from - to; dp[i][from][to] = t[from][to] + dp[i - 1][from][other] + dp[i - 1][other][to]; ll tmp = 2 * dp[i - 1][from][to] + dp[i - 1][to][from] + t[from][other] + t[other][to]; dp[i][from][to] = min(dp[i][from][to], tmp); } } } cout << dp[n][0][2] << endl; }