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