Codeforces Round #450 (Div. 2) E. Maximum Questions - 两个条件的DP

题目链接：https://codeforces.com/contest/900/problem/E
题目大意：
给你一个n和长度为n的字符串。只包含a b ?。和一个t。问你最少改变最少的？。让n字符串中出现不重复长度为t。ababa…的个数最多。

我们先考虑这么让前i个字符让t的个数f[i]达到最多。因为t在n出现一定是连续的。我们只要记录当前字符为a或者b连续a，b交替出来的字符串最长为多少就可以了。

if(c[i]=='a') h[0][i]=h[1][i-1]+1;
else if(c[i]=='b') h[1][i]=h[0][i-1]+1;
else {
    h[0][i]=h[1][i-1]+1;
    h[1][i]=h[0][i-1]+1;
}

只有最长>=m。f[i]=max( f[1]…f[i-m])+1
那么我们把f[i]定义为t在n中出现的前缀最大值次数。cut[i]定义为相应取得最大值时改变的最小数量。然后就是转移。cut[i]随着f[i]转移就可以了。cut[i]=max( f[1]…f[i-m])取得最大f[i]时的cut[i]加上i前m个字符中的？数量。

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

char c[100005];
int cut[100005], num[100005];
int f[100005], h[2][100005];

int main(){

    int n, m;
    scanf("%d%s%d", &n, c+1, &m);
    for(int i=1; i<=n; i++){
        num[i]=num[i-1];
        if(c[i]=='a') h[0][i]=h[1][i-1]+1;
        else if(c[i]=='b') h[1][i]=h[0][i-1]+1;
        else {
            h[0][i]=h[1][i-1]+1;
            h[1][i]=h[0][i-1]+1;
            num[i]++;
        }
        f[i]=f[i-1], cut[i]=cut[i-1];
        if(h[(m+1)&1][i]>=m){//数量增加时
            if(f[i]<f[i-m]+1){
                f[i]=f[i-m]+1, cut[i]=cut[i-m]+num[i]-num[i-m];
            }
            if(f[i]==f[i-m]+1){
                cut[i]=min(cut[i], cut[i-m]+num[i]-num[i-m]);
            }
        }
    }
    printf("%d\n", cut[n]);

    return 0;
}