鉄則本 A22 - Sugoroku (3Q, ★3)

一次元 DP で「配る DP」が書きやすい問題。鉄則本の問題なのでコードのみ。

• 問題へのリンク

問題概要

マス目に と記された マスの双六がある。1 からスタートして へ進みたい。

• マス からマス () に進むことができて：100pt 獲得
• マス からマス () に進むことができて：150pt 獲得

最大スコアを求めよ。

制約

• 

コード

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

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 = 1; i < N; i++) cin >> B[i];

    vector<int> dp(N+1, -INF);
    dp[1] = 0;
    for (int i = 0; i < N; i++) {
        if (A[i] <= N) chmax(dp[A[i]], dp[i] + 100);
        if (B[i] <= N) chmax(dp[B[i]], dp[i] + 150);
    }
    cout << dp[N] << endl;
}