cf 814C 思维

http://codeforces.com/contest/814/problem/C

给定一个字符串s，长度小于1500，进行q次询问q<=20w,每次询问输入一个m和一个字符c，求将最多m个c代替原来字符串的某些位置，能得到的连续个c的最长长度。

很容易想到一个n*n*q的暴力做法，但是会超时，由于只有26个字母，最长1500，考虑预处理所有结果。

枚举所有的字母，然后枚举所有的区间，预处理找出m个c对应的最佳区间长度。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define inf 0x3f3f3f3f
 4 int dp[26][1510]={0};
 5 int main()
 6 {
 7 
 8     int n,m,i,j,k,q;
 9     char s[1550],ch;
10     cin>>n>>(s+1)>>q;
11     for(int alp=0;alp<26;++alp)
12     {
13         for(i=1;i<=n;++i)
14         {
15             int tot=0;
16             for(j=i;j<=n;++j)
17             {
18                 if(s[j]-'a'!=alp) ++tot;
19                 dp[alp][tot]=max(dp[alp][tot],j-i+1);
20             }
21 
22         }
23         for(i=1;i<=n;++i) dp[alp][i]=max(dp[alp][i],dp[alp][i-1]);
24     }
25     while(q--){
26         scanf("%d %c",&m,&ch);
27         printf("%d
",dp[ch-'a'][m]);
28     }
29     return 0;
30 }