マルバツスタンプ (Circle Cross Stamps) [第18回日本情報オリンピック 予選 C]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/JOI/Prelim/0654?year=2019

前提知識

• 動的計画法

解説

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0654/judge/3757763/C++14

貪欲法でも行けそうな感じであるが、DPしておこう。
dp[i] := i番目までのマルバツスタンプの最大使用回数
S[i]!=S[i+1]であれば、マルバツスタンプが使えるので、+1で遷移させる。

int N; string S;
int dp[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
    rep(i, 0, N) {
        chmax(dp[i + 1], dp[i]);
        if (i + 1 < N and S[i] != S[i + 1]) chmax(dp[i + 2], dp[i] + 1);
    }
    cout << dp[N] << endl;
}