[yukicoder] No. 0921 ずんだアロー

2019年12月4日

問題

方針

大きさが異なっている隣り合う餅をずんだ餅にする場合

この場合、大きさが小さい餅が消えてしまうので適切ではありません。例えば、\( A = (1, 2, 3, 4, 5) \) の配列において、\( 1 \) 番目と \( 2 \) 番目をずんだ餅にすると、ずんだ餅が \( 1 \) つ得られますが、\( 3 \) 番目の餅をずんだ餅にしても消えてしまうので、\( B = (4, 5) \) という配列を考えることになります。つぎに、\( 1 \) 番目の餅だけをずんだ餅にすると、\( B = (3, 4, 5) \) という配列を考えることになります。

 大きさが同じ餅をまとめてずんだ餅にする場合

大きさが同じ餅をまとめてずんだ餅にする場合、餅を〇、ずんだ餅を×と表すと、最終的な餅の状況が “〇×〇〇×" や “×〇×〇" や “×〇〇×" のように×が連続しないように選ぶことが最適であることが分かります。しかし、大きさが同じ餅をまとめてずんだ餅にする方法は最適ではありません。

例えば、\( A = (1, 1, 2, 2, 2, 3, 3, 3) \) が与えられたとき、大きさが \( 1, 3 \) の餅をずんだ餅にすると、\( 5 \) 個のずんだ餅が得られますが、"××〇×〇×××" と選ぶと \( 6 \) 個のずんだ餅が得られます。

動的計画法

\( d_i \) を \( i \) 個まで餅を調べた時の得られるずんだ餅の最大値とします。初期値は、\( d_0 = 0, d_1 = 1 \) です。

\( A_{i – 1} = A_i \) のとき

このとき、\( d_i = d_{i – 1} + 1 \) となります。これは、\( i \) 番目の餅をずんだ餅にしても、前の餅と大きさが同じなので、消えることがないからです。

\( A_{i – 1} \neq A_i \) のとき

このとき、\( d_i = \max (d_{i – 1}, d_{i – 2} + 1) \) となります。これは、\( i \) 番目の餅をずんだ餅にしない場合とする場合を考えています。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    int A[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    int dp[N + 1]{};
    dp[1] = 1;
    for (int i = 1; i < N; i++) {
        if (A[i - 1] == A[i]) {
            dp[i + 1] = dp[i] + 1;
        } else {
            dp[i + 1] = max(dp[i], dp[i - 1] + 1);
        }
    }
    cout << dp[N] << "\n";
    return 0;
}