https://atcoder.jp/contests/dp/tasks/dp_c
前提知識
解説
https://atcoder.jp/contests/dp/submissions/3946364
DPだという前提で考えると、
dp[i] := i日目の活動を終えたときの幸福度の総和の最大値
というDPが思いつく。
しかし、これでは「2日以上連続で同じ活動を行うことはできない」という制約を解消できない。
そのため、情報を追加する必要がある。
最後の行動が特定できれば、制約をチェックできる。
そのため、これを組み込んで
dp[i][lst] := i日目の活動を終えて、最終日にlstをしたときの幸福度の総和の最大値
として、解く。
ABCを012と数値化してDPに落とし込もう。
遷移先は次の日に012のどれをやるかで3択である。
最終日と異なる行動のみ選択できるようにしよう。
int N, A[101010][3], dp[101010][3]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N) rep(j, 0, 3) cin >> A[i][j]; rep(lst, 0, 3) dp[1][lst] = A[0][lst]; rep(i, 1, N) rep(lst, 0, 3) { rep(nxt, 0, 3) if (lst != nxt) chmax(dp[i + 1][nxt], dp[i][lst] + A[i][nxt]); } int ans = 0; rep(lst, 0, 3) chmax(ans, dp[N][lst]); cout << ans << endl; }