http://codeforces.com/contest/814/problem/C
给定一个字符串s,长度小于1500,进行q次询问q<=20w,每次询问输入一个m和一个字符c,求将最多m个c代替原来字符串的某些位置,能得到的连续个c的最长长度。
很容易想到一个n*n*q的暴力做法,但是会超时,由于只有26个字母,最长1500,考虑预处理所有结果。
枚举所有的字母,然后枚举所有的区间,预处理找出m个c对应的最佳区间长度。
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int dp[][]={};
int main()
{ int n,m,i,j,k,q;
char s[],ch;
cin>>n>>(s+)>>q;
for(int alp=;alp<;++alp)
{
for(i=;i<=n;++i)
{
int tot=;
for(j=i;j<=n;++j)
{
if(s[j]-'a'!=alp) ++tot;
dp[alp][tot]=max(dp[alp][tot],j-i+);
} }
for(i=;i<=n;++i) dp[alp][i]=max(dp[alp][i],dp[alp][i-]);
}
while(q--){
scanf("%d %c",&m,&ch);
printf("%d\n",dp[ch-'a'][m]);
}
return ;
}