C. Unstable String(cf) dp

原题链接：Problem - 1535C - Codeforces

题目大意：

有t 组询问，每次给定一个仅包含字符 1 或 0 或 ？的字符串 s ss。定义一个子串是不稳定的当且仅当子串中任意相邻两数均不相同，如 101010…101010… 或 010101…010101…。其中 ? 可以变为 1 或 0 其中一种。请求出给定的 s ss 中最多可以有的不稳定子串个数。

注意：

1.？？是一个符合的子串而不是两个，因为它有情况可以满足beautiful串（01/10），但是并不是算2个，只是算一个。

2.每轮不要忘记置0！！dp[][]要置0！！

#include
using namespace std;
#define INF 0x3f3f3f3f
typedef pair PII;
const double pi = acos(-1.0);
#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define rrep(i, n) for (int i = n; i >= (1); --i)
typedef long long ll;
#define sqar(x) ((x)*(x))

const int N = 2e5 + 10;
int dp[N][2]; //一维坐标为字符串中每个数的坐标，表示以s[i]为右端点子串数目

int main(){
    int t;
    string s;
    cin >> t;
    while(t--){
        memset(dp, 0, sizeof dp); //记得置0
        cin >> s;
        int n = s.length();
        s = " " + s;
        ll res = 0;
        rep(i, n){
            if(s[i] == '0') dp[i][0] = dp[i - 1][1] + 1;
            else if(s[i] == '1') dp[i][1] = dp[i - 1][0] + 1;
            else{
                dp[i][0] = dp[i - 1][1] + 1;
                dp[i][1] = dp[i - 1][0] + 1;
            }
            res += max(dp[i][0], dp[i][1]); //其实如果？前面是0，那么其实它最后肯定是取[0]的那个大
        }  //？不是固定的，它在不同子串里可以代表不同的角色（0.1）
        //所以我们可以判定??是一个子串，而不是判定??为01/10两个子串
        //这也就是我们取max而不是取sum的原因
        printf("%lldn", res);
    }
    return 0;
}