题意：
给出一个长度为n只含有a和b还有‘?’的串s,且'?'可以被任意替换为a或b。再给出一个字符串t (奇数位上为a，偶数位上为b，所以在题目中只给出了t的长度m)，现在要求保证t在s中出现的次数最多的情况下面，使用'?'最小的情况使用了几个问号。
题解：
拿到这个题目可以看出是DP，但是比较难以解决的就是如何确定在第i个位置时前面m个字符能够满足t，这里我看了别人的题解 ～。～哇，震惊！首先的话先对‘?’做前缀和，然后设置两个数组s[2]分别表示在第i个位置前面交叉字符串的长度，这样的话第i步结尾为a(?)满足交叉字符串的最大长度就等于第i-1步结尾为b(?)的长度加1；
res[i] = res[i-] + (vec[i]=='?'); // ？前缀和
if(vec[i] != 'a') s[][i] = s[][i-] + ;
if(vec[i] != 'b') s[][i] = s[][i-] + ;
这样我们就求出了每一步是否满足能够形成t的条件，就可以开始DP了。（如果第i步满足就判断dp[i-m]+1和dp[i-1]）
#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5+;
char vec[MAX_N];
int res[MAX_N];
int s[][MAX_N];
int dp[MAX_N];
int cost[MAX_N];
int main()
{
int N,M,T;
memset(res,,sizeof(res));
scanf("%d%s%d",&N,vec+,&M); // 这里vec+1 可以把字符串赋予（1-n）
for(int i=; i<=N; i++)
{
res[i] = res[i-] + (vec[i]=='?');
if(vec[i] != 'a') s[][i] = s[][i-] + ;
if(vec[i] != 'b') s[][i] = s[][i-] + ;
if(s[M&][i] >= M)
{
dp[i] = dp[i-M]+;
cost[i] = cost[i-M] + res[i] - res[i-M];
}
else
{
dp[i] = dp[i-];
cost[i] = cost[i-];
}
if(dp[i] <= dp[i-])
{
if(dp[i] == dp[i-]) cost[i] = min(cost[i],cost[i-]);
else cost[i] = cost[i-];
}
}
cout<<cost[N]<<endl;
return ;
}
emmmm...这是cf大佬的写法～～ 也就比我短了一倍吧 @。@
#include<bits/stdc++.h>
#define N 100005
using namespace std;
char s[N];
int n,m,b[N],c[][N];
pair<int,int> f[N];
int main(){
scanf("%d%s%d",&n,s+,&m);
for (int i=;i<=n;i++){
b[i]=b[i-]+(s[i]=='?');
if (s[i]!='a') c[][i]=c[][i-]+;
if (s[i]!='b') c[][i]=c[][i-]+;
if (c[m&][i]>=m) f[i]=make_pair(f[i-m].first+,f[i-m].second-b[i]+b[i-m]);
f[i]=max(f[i],f[i-]);
}
printf("%d\n",-f[n].second);
}