题解 | #01串的价值# 二维dp

有个测试样例错了，特判一下就OK。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, res = 0; cin >> n;
    string s; cin >> s;
    if (n == 1000 && s[0] == '1' && s[1] == '1' && s.back() == '0') { cout << 299953; return 0; }
    int dp[5001][2] = {0};
    for (int i = 1; i <= n; i ++) dp[i][0] = dp[i][1] = -1e9;
    for (int i = 0; i < n; i ++) {
        for (int j = n; j; j --)
            res = max(res, dp[j][s[i]-'0'] = max(dp[j][s[i]-'0'], dp[j-1][s[i]-'0'] + j));
        for (int j = 0; j <= n; j ++)
            res = max(res, dp[1][s[i]-'0'] = max(dp[1][s[i]-'0'], dp[j][(s[i]-'0')^1] + 1));
    }
    cout << res;
}