codeforces 814 C. An impassioned circulation of affection 【尺取法 or DP】

//yy:因为这题多组数据，DP预处理存储状态比每次尺取快多了，但是我更喜欢这个尺取的思想。

题目链接：codeforces 814 C. An impassioned circulation of affection

题意：给出字符串长度n (1 ≤ n ≤ 1 500)，字符串s由小写字母组成,q个询问q (1 ≤ q ≤ 200 000)，每个询问为：m_i (1 ≤ m_i ≤ n) c_i，表示可以把任意mi个字母改成ci,求每次改变后只由ci组成的最长连续字串的长度。

解法一：尺取法：

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 const int N = 1500+5;
 6 char s[N];
 7 char c;
 8 int n, q, m;
 9 int main() {
10     scanf("%d %s", &n, s);
11     scanf("%d", &q);
12     while(q--) {
13         scanf("%d %c", &m, &c);
14         int l = 0, r = 0;
15         int ans = 0;
16         int cnt = 0;
17         while(r < n) {
18             if(cnt <= m) {
19                 if(s[r++] != c) cnt++;
20             }
21             if(cnt > m) {
22                 if(s[l++] != c) cnt--;
23             }
24             ans = max(ans, r - l);
25         }
26         printf("%d
", ans);
27     }
28     return 0;
29 }

997ms

解法二：DP：打个表，暴力枚举区间，求区间内字母i没有出现的个数j，然后dp[i][j]表示换成j个字母i所求的最长长度，每次询问直接输出即可。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 using namespace std;
 5 const int N = 1505;
 6 int dp[26][N];
 7 char s[N], c;
 8 int n, q, i, j, k, num, m;
 9 int main() {
10     scanf("%d %s %d", &n, s+1, &q);
11     for(k = 0; k < 26; ++k) {
12         for(i = 1; i <= n ; ++i) {
13             num = 0;
14             for(j = i; j <= n; ++j) {
15                 if(s[j]-'a' != k) num++;
16                 dp[k][num] = max(dp[k][num], j-i+1);
17             }
18         }
19         for(i = 1; i <= n; ++i)
20             dp[k][i] = max(dp[k][i], dp[k][i-1]);
21     }
22     while(q--) {
23         scanf("%d %c", &m, &c);
24         printf("%d
", dp[c-'a'][m]);
25     }
26     return 0;
27 }

156ms

解法三：还是DP。。。yy无聊打发时间。。。发呆

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 const int N = 1505;
 5 int dp[26][N];
 6 char s[N], c;
 7 int n, q, i, j, k, num, m;
 8 int main() {
 9     scanf("%d %s %d", &n, s+1, &q);
10     for(i = 0; i < 26; ++i)
11         for(j = 1; j <= n; ++j) dp[i][j] = j;
12     for(i = 1; i <= n; ++i) {
13         for(num = 0, j = i; j <= n; ++j) {
14             if(s[j] != s[i]) num++;
15             if(j-i+1 > dp[s[i]-'a'][num]) dp[s[i]-'a'][num] = j-i+1;
16         }
17     }
18     for(i = 1; i <= n; ++i) {
19         for(num = 0, j = n; j >= 1; --j) {
20             if(s[j] != s[i]) num++;
21             if(n-j+1 > dp[s[i]-'a'][num]) dp[s[i]-'a'][num] = n-j+1;
22         }
23     }
24     for(i = 0; i < 26; ++i)
25         for(j = 1; j <= n; ++j)
26             dp[i][j] = max(dp[i][j], dp[i][j-1]);
27     /*for(i = 0; i < 26; ++i)
28         for(j = 1;j <= n; ++j)
29             printf("%d	", dp[i][j]);
30         puts("");*/
31     while(q--) {
32         scanf("%d %c", &m, &c);
33         printf("%d
", dp[c-'a'][m]);
34     }
35     return 0;
36 }

109ms