删除字串

题目链接： https://www.nowcoder.com/acm/contest/79/C

思路是DP， dp[i][j][k] 表示到第i位为止变换次数为j次，且最后一个字母为k时的最大长度。(k==1时，整个串以b结尾，k==0时以a结尾)那么有

当前位置是a时

dp[i][j][0] = max(dp[i-1][j][0] + 1, dp[i-1][j-1][1]+1)

dp[i][j][1] = dp[i-1][j][1]

当前位置为b时有类似的状态转移方程，具体看代码。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 char s[100005];
 5 int a[100005];
 6 int dp[100005][11][2];
 7 int n, m;
 8 
 9 int main()
10 {
11     scanf("%d%d", &n, &m);
12     scanf("%s", s);
13     int i = 0;
14     while ( s[i] && s[i] == 'b')
15         ++i;
16     if (i == n)
17     {
18         printf("0
");
19         return 0;
20     }
21     /*
22 
23     memset(dp, 0, sizeof(dp));
24     dp[i][0][0] = 1;
25     for (++i; i < n; ++i)
26     {
27         dp[i][0][0] = dp[i-1][0][0] + (s[i]=='a'?1:0);
28         for (int j = 1; j <= m; ++j)
29         {
30             if (s[i] == 'a')
31             {
32                 dp[i][j][0] = max(dp[i-1][j][0] + 1, dp[i-1][j-1][1] + 1);
33                 dp[i][j][1] = dp[i-1][j][1];
34             }
35             else
36             {
37                 dp[i][j][1] = max(dp[i-1][j][1] + 1, dp[i-1][j-1][0] + 1);
38                 dp[i][j][0] = dp[i-1][j][0];
39             }
40         }
41     }
42     int ans = 0;
43     for (int i = 0; i < n; ++i)
44     {
45         for (int j = 0; j <=m; ++j)
46         {
47             ans = max(ans, dp[i][j][0]);
48             ans = max(ans, dp[i][j][1]);
49         }
50     }
51 
52 
53     */
54     int len = 1;
55     char ch = 'a';
56     int cnt = 0;
57     for (++i;i<n;++i)
58     {
59         if (s[i] == ch)
60         {
61             ++len;
62         }
63         else
64         {
65             a[cnt++] = len;
66             len = 1;
67             ch = s[i];
68         }
69     }
70     a[cnt++] = len;
71     memset(dp, 0, sizeof(dp));
72     dp[0][0][0] = a[0];
73     int ans = a[0];
74     for (int i = 1; i < cnt; ++i)
75     {
76         dp[i][0][0] = dp[i-1][0][0] + ((i&1)?0:a[i]);
77         // dp[i][0][1] = 0;
78         for (int j = 1; j <= m; ++j)
79         {
80             if (i&1) // 'b'
81             {
82                 dp[i][j][1] = max(dp[i-1][j][1] + a[i], dp[i-1][j-1][0] + a[i]);
83                 dp[i][j][0] = dp[i-1][j][0];
84             }
85             else
86             {
87                 dp[i][j][0] = max(dp[i-1][j][0] + a[i], dp[i-1][j-1][1] + a[i]);
88                 dp[i][j][1] = dp[i-1][j][1];
89             }
90             ans = max(ans, dp[i][j][0]);
91             ans = max(ans, dp[i][j][1]);
92         }
93         ans = max(ans, dp[i][0][0]);
94         ans = max(ans, dp[i][0][1]);
95     }
96     printf("%d
", ans);
97     return 0;
98 }