ちまちまとDPする問題。

A. Alternative Thinking

問題

0と1のみからなる列が与えられる。 この列の連続する部分文字列をひとつ好きに選んで、その部分の0と1を入れ換える。 そうしてできた列の必ずしも連続しない部分列で、同じ文字が隣り合わない列(e.g. 0101, 010101010101010)の、最長の長さを求めよ。

解法

dp[何文字目まで使ったか][反転をする区間の前/中/後][最後に採用した文字] = 部分列の長さでdp。$O(n)$。

実装

ちょっと重い。

#include <iostream>
#include <vector>
#include <array>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
int main() {
    int n; cin >> n;
    string s; cin >> s;
    constexpr int before_flip = 0;
    constexpr int in_flip = 1;
    constexpr int after_flip = 2;
    vector<array<array<int,2>,3> > dp(s.length()+1);
    dp[0][0][0] = 0;
    dp[0][0][1] = 0;
    repeat (i,s.length()) {
        repeat (j,3) {
            repeat (k,2) {
                dp[i+1][j][k] = dp[i][j][k];
            }
            int k = s[i]-'0';
            dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][not k]+1);
            if (j == before_flip) {
                // nop
            } else if (j == in_flip) {
                dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][before_flip][k]+1);
            } else if (j == after_flip) {
                dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][in_flip][k]+1);
            }
        }
    }
    int result = 0;
    repeat (j,3) {
        repeat (k,2) {
            result = max(result, dp[s.length()][j][k]);
        }
    }
    cout << result << endl;
    return 0;
}