题目大意
给你一个长度为n的字符串S, 只包含小写字母, q个请求, 每个请求由m c构成, 问改变字符串中的m个字母, 求只包含字母c的最长连续子串长度是多少
解题思路
设sum[ch][i] := S前i个字母包含字符ch的个数, 预处理出这个, 可以快速求出任意区间内某字母的个数 dp[ch][i] := 改变i个字符, 最长的只包含ch的子串的长度 对于区间[i, j], 字母k, 有dp[k][ j-i+1 - (sum[k][j]-sum[k][i-1]) ] = max(dp[k][ j-i+1 - (sum[k][j]-sum[k][i-1]) ], j-i+1); (j-i+1 - (sum[k][j]-sum[k][i-1])表示在区间[i, j]中, 要把区间全部填成字母k, 需要改变的字符数量) 两重循环处理完所有区间[i, j]后, dp数组还有一些值没有更新过, 一直为零 同时, 如果更改i个字母得到最长只含有字符j的子串长度为len, 那么更改i+1个能得到的子串长度一定大于等于len+1, dp[j][i] = max(dp[j][i], dp[j][i-1]+1);, 这个很容易理解 最后dp的值不能大于n
代码
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN =
2000;
int n, q, dp[
30][MAXN], sum[
30][MAXN], m;
char s[MAXN], col[
20];
int main()
{
scanf(
"%d%s", &n, s+
1);
for(
int i=
1; i<=n; ++i)
{
for(
int j=
0; j<
26; ++j)
sum[j][i] = sum[j][i-
1];
sum[s[i]-
'a'][i] +=
1;
}
memset(dp,
0,
sizeof(dp));
for(
int i=
1; i<=n; ++i)
{
for(
int j=i; j<=n; ++j)
{
for(
int k=
0; k<
26; ++k)
{
dp[k][ j-i+
1 - (sum[k][j]-sum[k][i-
1]) ]
= max(dp[k][ j-i+
1 - (sum[k][j]-sum[k][i-
1]) ], j-i+
1);
}
}
}
for(
int i=
1; i<=n; ++i)
for(
int j=
0; j<
26; ++j) dp[j][i] = max(dp[j][i], dp[j][i-
1]+
1);
scanf(
"%d", &q);
for(
int i=
0; i<q; ++i)
{
scanf(
"%d%s", &m, col);
printf(
"%d\n", dp[col[
0]-
'a'][m] > n ? n : dp[col[
0]-
'a'][m]);
}
return 0;
}
