Day4T4

日常竞赛测试讨论
,
1

problemId:15778

Day4 T4

题意：

定义一个字符串 s 中字符 c 的价值为 s 中出现的连续字符 c 的个数。

现在对于一个询问，给出一个字符 c_i 和数字 $m_i$，表示最多修改字符串中的 m_i 个字符，问字符 c_i 的价值最大为多少。

思路：

24分：

暴力，对于每个 c_i 双指针维护区间，然后每次取 \max 即可。

28分：

把 while(q--) 改成 for (int C = 1; C <= q; ++C) 即可。

满分：

设 f_{i,j} 表示第 i 个字符，操作了 j 次的最大个数。

那么，$f_{i,j}=\max_{\text{区间不是i的个数为j的区间}} r-l+1$

然后不是字符 i 的话就搞个前缀和枚举一下即可。

最后还要 $f_{i,j} = \max f_{i-1,j}$，因为有可能他操作次数太多，但不是 i 字符的太少，无法更新，所以最后要更新一下。

\text{AC Code}

#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
char s[N], c[30];
int n, m, q, dp[30][N], sum[N][30];
int main() {
    cin >> n >> s + 1;

    for (int i = 1; i <= n; i ++)
        for (int j = 0; j < 26; j ++)
            sum[i][j] = sum[i - 1][j] + (s[i] - 'a' == j);

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= i; j ++) {
            for (int k = 0; k < 26; k ++) {
                int tot = (i - j + 1) - (sum[i][k] - sum[j - 1][k]);
                dp[k][tot] = max(dp[k][tot], i - j + 1);
            }
        }
    }

    for (int i = 0; i < 26; i ++)
        for (int j = 1; j <= n; j ++)
            dp[i][j] = max(dp[i][j], dp[i][j - 1]);

    scanf("%d", &m);

    for (int i = 1; i <= m; i ++) {
        scanf("%d %s", &q, c);
        printf("%d\n", dp[c[0] - 'a'][q]);
    }

    return 0;
}