ACM模版

描述


题解

对于这种海量查询的问题，不用多想，99 成需要预处理，而常见的预处理手段除了线段树、树状数组、RMQ 之类，还有 DP 等等，这里用的就是 DP 预处理。

设 dp[i][j] 表示对于字符 i 进行 j 次修改的最优解，初始化 dp[i][j]=j ，因为不管序列如何，我们都可以肯定的是经过 j 次修改至少有 j 个连续的字符 i <script type="math/tex" id="MathJax-Element-127">i</script>。

其他就没有什么可说的了~~~

代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int MAXN = 1555;
const int MAXC = 26;

int n, q;
char str[MAXN];
int dp[MAXC][MAXN];

int main()
{
    while (cin >> n)
    {
        memset(dp, 0, sizeof(dp));

        scanf("%s", str);

        for (int i = 0; i < MAXC; i++)
        {
            for (int j = 0; j <= n; j++)
            {
                dp[i][j] = j;
            }
        }

        for (int i = 0; i < n; i++)
        {
            int c = str[i] - 'a';
            int tmp = 1, k = i + 1;
            dp[c][0] = 1;
            for (int j = 0; j <= n; )
            {
                if (k >= n || str[i] != str[k])
                {
                    j++;
                }
                tmp++;
                if (tmp == n)
                {
                    while (j <= n)
                    {
                        dp[c][j++] = n;
                    }
                    break;
                }
                dp[c][j] = max(dp[c][j], tmp);
                k++;
            }
        }

        cin >> q;

        int m;
        char c[3];
        while (q--)
        {
            scanf("%d%s", &m, c);
            printf("%d\n", dp[c[0] - 'a'][m]);
        }
    }

    return 0;
}