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;
}