はまやんはまやんはまやん

hamayanhamayan's blog

東京と京都 [yukicoder No.561]

https://yukicoder.me/problems/no/561

解説放送

準備中

解説

https://yukicoder.me/submissions/199824

dp[day][place] := day日目でplace(0=tokyo|1=kyoto)場所にいるときの増やせる金額の最大値
これを更新していく
場所を変えないなら dp[day + 1][place] = max(dp[day + 1][place], dp[day][place] + C[day][place])
場所を変えるなら dp[day + 1][1-place] = max(dp[day + 1][1-place], dp[day][place] + C[day][1-place] - D)
これで最終的に東京と京都にいる時の最大値を取れば答え。

typedef long long ll;
#define INF 1LL<<60
int N;
ll D, C[101][2];
ll dp[101][2];
// dp[day][0=tokyo|1=kyoto]
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> D;
    rep(i, 0, N) cin >> C[i][0] >> C[i][1];
    rep(i, 0, N + 1) rep(j, 0, 2) dp[i][j] = -INF;

    dp[0][0] = 0;
    dp[0][1] = -D;
    rep(d, 0, N) rep(p, 0, 2) {
        dp[d + 1][p] = max(dp[d + 1][p], dp[d][p] + C[d][p]);
        dp[d + 1][1 - p] = max(dp[d + 1][1 - p], dp[d][p] + C[d][1 - p] - D);
    }

    ll ans = max(dp[N][0], dp[N][1]);
    cout << ans << endl;
}