鉄則本 A17 - Dungeon 2 (3Q, ★3)

DP の経路復元を学ぶ問題。鉄則本の問題なのでコードのみ。

• 問題へのリンク

問題概要

あるダンジョンには 個の部屋があり、 と番号がついている。このダンジョンは一方通行であり、通路を介して 1 つ先または 2 つ先の部屋に移動することができる。各通路における移動時間は以下の通り。

• 部屋 から部屋 ： 分
• 部屋 から部屋 ： 分

太郎君が部屋 1 から部屋 へ最短時間で移動する方法を 1 つ出力するプログラムを作成せよ。

制約

• 

コード

#include <bits/stdc++.h>
using namespace std;
template<class S, class T> inline bool chmin(S &a, T b) { return (a > b ? a = b, 1 : 0); }
const int INF = 1<<30;

int main() {
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    for (int i = 1; i < N; i++) cin >> A[i];
    for (int i = 2; i < N; i++) cin >> B[i];

    vector<int> dp(N, INF), pre(N, -1);
    dp[0] = 0;
    for (int i = 0; i < N; i++) {
        if (i-1 >= 0 && chmin(dp[i], dp[i-1] + A[i])) pre[i] = i-1;
        if (i-2 >= 0 && chmin(dp[i], dp[i-2] + B[i])) pre[i] = i-2;
    }

    vector<int> res({N-1});
    int s = N-1;
    while (true) {
        s = pre[s];
        if (s == -1) break;
        res.push_back(s);
    }
    reverse(res.begin(), res.end());
    cout << res.size() << endl;
    for (auto v : res) cout << v+1 << " ";
    cout << endl;
}