CF814C An impassioned circulation of affection

思路：

对于题目中的一个查询(m, c)，枚举子区间[l, r](0 <= l <= r < n)，若该区间满足其中的非c字符个数x不超过m，则可以将其合法转换为一个长度为r-l+1的全c子序列，可以使用动态规划以O(n²)的复杂度计算，然而O(n²q)的复杂度还是太高了。于是先离线把26n中情况都计算出来，再打表即可。复杂度O(26n²+q)。

实现：

 #include <iostream>

 #include <cstdio>

 using namespace std;

 const int MAXN = ;

 int n, q, m, ans[][MAXN];

 string s;

 char c;

 int main()

 {

     cin >> n >> s;

     for (int k = ; k < ; k++)

     {

         char tmp = 'a' + k;

         for (int i = ; i < n; i++)

         {

             int cnt = ;

             for (int j = i; j < n; j++)

             {

                 if (s[j] != tmp) cnt++;

                 ans[k][cnt] = max(ans[k][cnt], j - i + );

             }

         }

         for (int i = ; i < MAXN; i++)

             ans[k][i] = max(ans[k][i], ans[k][i - ]);

     }

     cin >> q;

     for (int i = ; i < q; i++)

     {

         scanf("%d %c", &m, &c);

         printf("%d\n", ans[c - 'a'][m]);

     }

 }

巴特西

CF814C An impassioned circulation of affection

最新文章

热门文章