采用记忆化搜索的形式较容易解决本题, 以下代码由zhouzhiyuan提供
#include <bits/stdc++.h>
using namespace std;
int n, k;
char c;
int ff[100005], f[100005][25][5];
int dfs(int x, int y, int z) {
if (x == 0)
return 0;
if (f[x][y][z] != 0)
return f[x][y][z];
int s = dfs(x - 1, y, z);
if (y != 0) {
if (z != 0)
s = max(s, dfs(x - 1, y - 1, 0));
if (z != 1)
s = max(s, dfs(x - 1, y - 1, 1));
if (z != 2)
s = max(s, dfs(x - 1, y - 1, 2));
}
if (z == ff[x])
s++;
f[x][y][z] = s;
return f[x][y][z];
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
cin >> c;
if (c == 'P')
ff[i] = 0;
else if (c == 'H')
ff[i] = 1;
else
ff[i] = 2;
}
int s = 0;
for (int i = 0; i <= k; i++) {
s = max(s, max(dfs(n, i, 1), max(dfs(n, i, 2), dfs(n, i, 0))));
}
printf("%d", s);
}