12
ooyomioomioo21 o2 o这题我是用dp解的，不过好像很慢，比赛的时候算了下不会mle，就没滚动数组了。
dp[i][k][ch]表示以第i位结尾，允许变化k次，所求的字符是ch时的最大连续数量。
如果k > 0，那么dp[i][k][ch] > 0的，因为肯定可以把第i位变了。
那么对于第i位来说，如果str[i]和ch相同，那么应该是dp[i][k][ch] = dp[i - 1][k][ch] + 1，就是和上一段可以结合。而且不用花费变化次数，如果不同，那么需要把str[i]变成ch，才能和前面那一段结合，就是dp[i][k][ch] = dp[i - 1][k - 1][ch] + 1
复杂度n^2 * 26
#include#define IOS ios::sync_with_stdio(false)using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;char str[2222];int lenstr;//void dfs(char ch, int cur, int nowLen, int did, bool can) {// if (did > lenstr) return;// dp[ch][did] = max(dp[ch][did], nowLen);// if (dp[ch][did] > nowLen && nowLen && can) return;// if (cur > lenstr) return;// if (str[cur] == ch) {// dfs(ch, cur + 1, nowLen + 1, did, false);// } else {// dfs(ch, cur + 1, 0, did, false);// dfs(ch, cur + 1, nowLen + 1, did + 1, true);//// }//}int dp[1500 + 2][1500 + 2][26 + 1];int ans[1500 + 2][26 + 1];void work() { int n; scanf("%d", &n); scanf("%s", str + 1); lenstr = strlen(str + 1); for (int ch = 0; ch < 26; ++ch) { char cmp = ch + 'a'; for (int i = 1; i <= lenstr; ++i) { for (int k = 0; k <= lenstr; ++k) { if (cmp == str[i]) { dp[i][k][ch] = dp[i - 1][k][ch] + 1; } else if (k) dp[i][k][ch] = dp[i - 1][k - 1][ch] + 1; } } for (int k = 1; k <= lenstr; ++k) { int mx = 0; for (int i = 1; i <= lenstr; ++i) { mx = max(mx, dp[i][k][ch]); } ans[k][ch] = mx; } }// cout << dp[2][0]['o' - 'a'] << endl;// cout << dp[3][1]['o' - 'a'] << endl;// cout << dp[4][1]['o' - 'a'] << endl; int q; scanf("%d", &q); while (q--) { char s[22]; int m; scanf("%d%s", &m, s); printf("%d\n", ans[m][s[0] - 'a']); }}int main() {#ifdef local freopen("data.txt", "r", stdin);// freopen("data.txt", "w", stdout);#endif work(); return 0;}