【集训DAY18】Welcome J and Z 【动态规划】

思路：

我们可以设fi,j,k表示到了第i个，有j个j，k个z的最大答案。
然后nk^2转移

$code$

#include<iostream>
#include<cstring>
#include<cstdio>

using namespace std;

int n, k;
char s[1000];
int f[510][110][110];

int main() {
    
	scanf("%d%d", &n, &k);
	scanf("%s", s + 1);
	memset(f, -0x3f, sizeof(f));
	f[0][0][0] = 0, f[1][0][0] = 0;
	if(s[1] == 'j') f[1][1][0] = 0;
	else f[1][0][1] = 0;
	for(int i = 2; i <= n; i ++) {
    
		for(int j = 0; j <= k; j ++) {
    
			for(int g = 0; g <= k; g ++) {
    
				f[i][j][g] = f[i - 1][j][g];
				if(i >= 2 && s[i - 1] == 'j' && s[i] == 'z')
					f[i][j][g] = max(f[i][j][g], f[i - 2][j][g] + 1);
				if(i >= 1 && s[i - 1] == 'j' && s[i] == 'j' && j >= 1)
					f[i][j][g] = max(f[i][j][g], f[i - 2][j - 1][g] + 1);
				if(i >= 1 && s[i - 1] == 'z' && s[i] == 'z' && g >= 1)
					f[i][j][g] = max(f[i][j][g], f[i - 2][j][g - 1] + 1);
				if(i >= 1 && s[i - 1] == 'z' && s[i] == 'j' && g >= 1 && j >= 1)
					f[i][j][g] = max(f[i][j][g], f[i - 2][j - 1][g - 1] + 1);
			}
		}
	}
	int ans = 0;
	for(int i = 0; i <= k; i ++)
	ans = max(ans, f[n][i][i]);
	printf("%d", ans);
	return 0;
}