洛谷1136 迎接仪式

Posted by yjjr's blog on February 6, 2018

标签:区间DP

题目描述

LHX教主要来X市指导OI学习工作了。为了迎接教主,在一条道路旁,一群Orz教主er穿着文化衫站在道路两旁迎接教主,每件文化衫上都印着大字。一旁的Orzer依次摆出“欢迎欢迎欢迎欢迎……”的大字,但是领队突然发现,另一旁穿着“教”和“主”字文化衫的Orzer却不太和谐

为了简单描述这个不和谐的队列,我们用“j”替代“教”,“z”替代“主”。而一个“j”与“z”组成的序列则可以描述当前的队列。为了让教主看得尽量舒服,你必须调整队列,使得“jz”子串尽量多。每次调整你可以交换任意位置上的两个人,也就是序列中任意位置上的两个字母。而因为教主马上就来了,时间仅够最多作K次调整(当然可以调整不满K次),所以这个问题交给了你。

输入输出格式

输入格式:

输入文件welcome.in的第1行包含2个正整数N与K,表示了序列长度与最多交换次数。

第2行包含了一个长度为N的字符串,字符串仅由字母“j”与字母“z”组成,描述了这个序列。

输出格式:

输出文件welcome.out仅包括一个非负整数,为调整最多K次后最后最多能出现多少个“jz”子串。

输入输出样例

输入样例#1:

5 2

zzzjj

输出样例#1:

2

说明

【样例说明】

第1次交换位置1上的z和位置4上的j,变为jzzzj;

第2次交换位置4上的z和位置5上的j,变为jzzjz。

最后的串有2个“jz”子串。

【数据规模与约定】

对于10%的数据,有N≤10;

对于30%的数据,有K≤10;

对于40%的数据,有N≤50;

对于100%的数据,有N≤500,K≤100。

 

分析:

给定:长度为N的字符串

求:max{num”jz”}(字符串中“jz”这个子串最多个数)

满足:交换任意两个字符的次数<=k


贪心:从前往后找到第一个未形成“jz”的z,将第一个“z”换成当前第一个未形成”jz“的“j”

Eg.

Zzzjj

P=2,q=4;

jzzzj

P=4 q=5

符合样例,但是只有20分

显然这种n<=500的数据范围是不可能贪心的,反例如下

7 1

Jjjzzzj


正解:DP

F[i][j1][j2]表示前i个字符,改变了j1个‘j’和j2个’z’后的’jz’个数

状态转移方程

F[i][j1][j2]=max(f[i-1][j1][j2],  //未做任何变动

            F[i-2][j1-1][j2]+1  //s[i]=j,s[i-1]=j的情况(就是“jj”)

            F[i-2][j1][j2-1]+1  //s[i]=z,s[i-1]=z(两个z的情况)

            F[i-2][j1-1][j2-1]+1  )//s[i]=j,s[i-1]=z (“zj”的情况)

Ans=max(f[i][j1][j2]) (满足j1=j2)

 

Code

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define mem(x,num) memset(x,num,sizeof x)
#define LL long long
using namespace std;
const int maxn=506,maxk=106,inf=0x3f3f3f;
char s[maxn];
int f[maxn][maxk][maxk],n,k,ans=0;

int main()
{
	scanf("%d%d",&n,&k);
	scanf("%s",s+1);
	mem(f,-inf);
	f[0][0][0]=f[1][0][0]=0;
	if(s[1]=='j')f[1][1][0]=0;
	else f[1][0][1]=0;
	rep(i,2,n)
	    rep(j1,0,k)
	        rep(j2,0,k){
	        	f[i][j1][j2]=f[i-1][j1][j2];
	        	if(s[i]=='z'&&s[i-1]=='j')f[i][j1][j2]=max(f[i][j1][j2],f[i-2][j1][j2]+1);
	        	if(s[i]=='z'&&s[i-1]=='z'&&j2)f[i][j1][j2]=max(f[i][j1][j2],f[i-2][j1][j2-1]+1);
	        	if(s[i]=='j'&&s[i-1]=='j'&&j1)f[i][j1][j2]=max(f[i][j1][j2],f[i-2][j1-1][j2]+1);
	        	if(s[i]=='j'&&s[i-1]=='z'&&j1&&j2)f[i][j1][j2]=max(f[i][j1][j2],f[i-2][j1-1][j2-1]+1);
	        	if(j1==j2)ans=max(ans,f[i][j1][j2]);
	        }
	printf("%d\n",ans);
	return 0;
}



本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr