Vacation [Educational DP Contest / DP まとめコンテスト C]

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