ARC 197

Table of Contents

A - Operations on a Stack

https://atcoder.jp/contests/arc194/tasks/arc194_a

$d(i,1)$ を $i$ 番目の要素を使うときの総和の最大値、$d(i,0)$ を $i$ 番目の要素を使わないときの総和の最大値とする。

$i$ 番目の要素を使うとき、$i-1$ 番目の要素を使う場合、使わない場合の値いずれかの場合からの遷移がある。

$i$ 番目の要素を使わないとき、$i-1$ 番目の要素を積んで、その後その要素を捨てる操作になるから、$i-2$ 番目の要素を使う場合、使わない場合のうちの大きい方の値を選べばよい。

\begin{align} d(i,1) &= \max(dp(i-1, 1), dp(i-1, 0)) + A_i \nonumber \\ d(i,0) &= \max(dp(i-2, 1), dp(i-2, 0)) \nonumber \end{align}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vll a(n + 1);
    rep(i, n) cin >> a[i + 1];

    vvll dp(n + 1, vll(2, -INF));
    dp[0][1] = 0;
    rep2(i, 1, n + 1) {
        chmax(dp[i][1], dp[i - 1][1] + a[i]);
        chmax(dp[i][1], dp[i - 1][0] + a[i]);
        if (i - 2 >= 0) {
            chmax(dp[i][0], dp[i - 2][1]);
            chmax(dp[i][0], dp[i - 2][0]);
        }
    }
    cout << max(dp[n][0], dp[n][1]) << '\n';
}