[题解][洛谷P1136] 迎接仪式

题目描述

对于一个由字母“j”和“z”组成的字符串，可以任意交换两个字符的位置不超过k次，求最多能出现多少个“jz”字串。

题解

动态规划题。
设f[i][j][k][0/1]表示到第i位，前面交换了j个“j”，交换了k个“z”，且第i位是j（用0表示）或z（用1表示）。
当j=k时即为可行解。
为什么需要用第四维统计：因为上一位的末尾是0或1会对下一位产生影响。上一位既有被更改的可能，也有没有更改的可能，需分别计算。

代码

#include<bits/stdc++.h>
using namespace std;
int f[507][107][107][2];
int a[507];
int main(){
	memset(f,-1,sizeof f);
	int n,k;
	cin>>n>>k;
	string s;
    cin>>s;
	for(int i=1;i<=n;i++)a[i]= s[i-1]=='z';
	f[0][0][0][1]=0;
	for(int i=1;i<=n;i++)
		for(int p=0;p<=k;p++)
			for(int q=0;q<=k;q++){
				f[i][p][q][a[i]]=max(f[i-1][p][q][0]+a[i],f[i-1][p][q][1]);
				if(a[i]&&p)f[i][p][q][0]=max(f[i-1][p-1][q][1],f[i-1][p-1][q][0]);
				else if(!a[i]&&q)f[i][p][q][1]=max(f[i-1][p][q-1][0]+1,f[i-1][p][q-1][1]);
			}		
	int ans=0;
	for(int i=0;i<=k;i++)ans=max(ans,max(f[n][i][i][0],f[n][i][i][1]));
	cout<<ans<<endl;
}