题目链接：
http://codeforces.com/contest/814/problem/C
题意：
给出一个长为n的字符串s，接下来有q次询问，每次询问给出正整数m和字符c，问在字符串中最多添加m个字符c后字符串中最长的仅含c的连续子串的长度为多少
题解：
因为q<=2e5所以易想到这题需要将答案保存到数组中，这样就需要dp处理字符串
设dp[i][j][k]为从第i个下标开始选择修改k个字符后，仅含字符'a'+j的连续子串的最长长度为多少。
当i>=1，dp[i][j][k] = dp[i-1][j][k-p] （当s[i]=='a'+j时p=0，否则p=1）
当i==0，dp[i][j][k] = q （当k大于0或s[i]=='a'+j时q=1否则q=0）
然后因为给出m与c后dp的第一位无意义，所以可以舍去将dp[i][j][k]中有用的信息保存为ans[i][j]，ans[i][j]表示修改i个字符为'a'+j字符后字符串的仅含'a'+j的连续子串最长长度
#include<bits/stdc++.h> using namespace std; #define MAX_N 40005 #define inf 0x3f3f3f3f #define LL long long #define uLL unsigned long long const LL mod = 1e9+7; const LL INF = 1e18; typedef pair<int, int>P; const double eps = 1e-6; int dp[1505][26][1505]; int ans[1505][26]; int main() { int n; scanf("%d", &n); char s[1505]; scanf("%s", s); memset(dp, 0, sizeof(dp)); memset(ans, 0, sizeof(ans)); for(int i=0; i<n; i++) { for(int j=0; j<26; j++) { for(int k=0; k<=n; k++) { if(i) { if(k) dp[i][j][k] = dp[i-1][j][k-(s[i]!=('a'+j))] + 1; else dp[i][j][k] = (s[i]=='a'+j)?(1 + dp[i-1][j][k]):0; } else { if(s[i]=='a'+j) dp[i][j][k] = 1; else dp[i][j][k] = (k>0); } } } } for(int i=0; i<26; i++) { for(int j=0; j<n; j++) { for(int k=0; k<=n; k++) { ans[k][i] = max(ans[k][i], dp[j][i][k]); } } } int q; scanf("%d", &q); while(q--) { int m; char c; scanf("%d %c", &m, &c); printf("%d\n", ans[m][c-'a']); } }
再提供另一种尺取法，更好编码和理解
#include<bits/stdc++.h> using namespace std; #define MAX_N 40005 #define inf 0x3f3f3f3f #define LL long long #define uLL unsigned long long const LL mod = 1e9+7; const LL INF = 1e18; typedef pair<int, int>P; const double eps = 1e-6; int dp[26][1505]; int n, q; string s; void init() { for(int i=0; i<26; i++) { for(int j=1; j<=n; j++) { char c = ('a'+i); int l = 0; int r = 0; int tmp = s[0]!=c; int ans = 0; while(r>=l && r<n) { if(j>=tmp) ans = max(ans, r-l+1); if(j>=tmp) { r++; tmp += (s[r]!=c); } else { tmp -= (s[l]!=c); l++; } } dp[i][j] = ans; } } } int main() { cin >> n; cin >> s; cin >> q; init(); while(q--) { int m; char c; scanf("%d %c", &m ,&c); printf("%d\n", dp[c-'a'][m]); } }
