Codeforces Round #575 (Div. 3) D2. RGB Substring (hard version) 【递推】

一、题目

二、分析

　　思路一开始就想的对的，但是，用memset给数组初始化为0超时了！超时了！

　　然后我按照题解改了个vector初始化，就过了！

　　以后得谨慎使用memset了。

三、AC代码

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 #define ll long long
 5 #define Min(a,b) (a)>(b)?(b):(a)
 6 const int maxn = 2e5 + 13;
 7 char S[maxn];
 8 char Q[] = "GBR";
 9 int n, k;
10 
11 int main()
12 {
13     //freopen("input.txt", "r", stdin);
14     int q;
15     scanf("%d", &q);
16     while(q--)
17     {
18         int ans;
19         scanf("%d%d", &n, &k);
20         scanf("%s", S);
21         ans = k;
22         for(int i = 0; i < 3; i++)
23         {
24             vector<int> dp(n);
25             int p = i, j;
26             int res = 0;
27             for(j = 0; j < k; j++)
28             {
29                 if(S[j] != Q[p%3])
30                 {
31                     res++;
32                     dp[j] = 1;
33                 }
34                 p++;
35             }
36             ans = Min(ans, res);
37             for(j; j < n; j++)
38             {
39                 if(S[j] != Q[p%3])
40                 {
41                     res = res - dp[j - k] + 1;
42                     dp[j] = 1;
43                 }
44                 else
45                 {
46                     res = res - dp[j - k];
47                 }
48                 ans = Min(ans, res);
49                 p++;
50             }
51         }
52         printf("%d
", ans);
53     }
54     return 0;
55 }