P1136 迎接仪式
题目描述
LHX教主要来X市指导OI学习工作了。为了迎接教主，在一条道路旁，一群Orz教主er穿着文化衫站在道路两旁迎接教主，每件文化衫上都印着大字。一旁的Orzer依次摆出“欢迎欢迎欢迎欢迎……”的大字，但是领队突然发现，另一旁穿着“教”和“主”字文化衫的Orzer却不太和谐。
为了简单描述这个不和谐的队列，我们用“(j)”替代“教”，“(z)”替代“主”。而一个“(j)”与“(z)”组成的序列则可以描述当前的队列。为了让教主看得尽量舒服，你必须调整队列，使得“(jz)”子串尽量多。每次调整你可以交换任意位置上的两个人，也就是序列中任意位置上的两个字母。而因为教主马上就来了，时间仅够最多作(K)次调整（当然可以调整不满(K)次），所以这个问题交给了你。
输入输出格式
输入格式：
第一行包含(2)个正整数(N)与(K)，表示了序列长度与最多交换次数。
第二行包含了一个长度为(N)的字符串，字符串仅由字母“(j)”与字母“(z)”组成，描述了这个序列。
输出格式：
一个非负整数，为调整最多(K)次后最后最多能出现多少个“(jz)”子串。
数据规模与约定
对于(10\%)的数据，有(N≤10)；
对于(30\%)的数据，有(K≤10)；
对于(40\%)的数据，有(N≤50)；
对于(100\%)的数据，有(N≤500,K≤100)。
神题啊，膜拜膜拜~~
看起来就是地痞，考虑一下如何把状态都给丢进去
因为一次涉及两个地方的位置，所以我们很难把这样的状态准确表示。
我们可以考虑先找一些特殊的突破点或者显然成立的贪心性质
说到特殊，这个序列的字符集只有(2)
说道性质，很显然，一个位置不会被改两次，两个一样字符的不会被改。
以上是我开了上帝视角得出的，事实上，我们可能可以想到它们，但是它们不一定会真正启发到我们
还是要看做题积累的经验
下面上正解：
(dp_{i,j,k})代表在位置(i),('j')这个字符被交换过(j)次，('z')这个字符被交换过(k)次
请注意，这个交换是存在匹配的，但我们只管匹配，并不在乎具体谁和谁交换过
如果你没能理解上面这句话，请看看状态转移方程
因为一个匹配需要两个字符，所以我们从(当前位置-2)的地方之前进行更新
dp[i][j][k]=dp[i-1][j][k];
if(s[i]=='j'&&s[i-1]=='z'&&j&&k)
dp[i][j][k]=max(dp[i][j][k],dp[i-2][j-1][k-1]+1);
if(s[i]=='z'&&s[i-1]=='j')
dp[i][j][k]=max(dp[i][j][k],dp[i-2][j][k]+1);
if(s[i]=='j'&&s[i-1]=='j'&&j)
dp[i][j][k]=max(dp[i][j][k],dp[i-2][j-1][k]+1);
if(s[i]=='z'&&s[i-1]=='z'&&k)
dp[i][j][k]=max(dp[i][j][k],dp[i-2][j][k-1]+1);
if(j==k) ans=max(ans,dp[i][j][k]);
格外注意一下答案更新的地方，相等时更新代表什么，其实就是代表匹配上去了，这些东西都在互有交换，但现在交换次数一样了，所以我们可以更新答案
值得一提的是，我们其实并没有单以位置划分状态，可以注意到，匹配的位置是前后都有的，我们是把位置和交换的状态放在一起，才做到了无后效性
个人拙见，如有错误，烦请提出
Code:
#include <cstdio>
#include <cstring>
int max(int x,int y){return x>y?x:y;}
const int N=502;
int dp[N][103][103],n,m,ans;
char s[N];
int main()
{
scanf("%d%d%s",&n,&m,s+1);
memset(dp,-0x3f,sizeof(dp));
dp[0][0][0]=dp[1][0][0]=dp[1][s[1]=='j'][s[1]=='z']=0;
for(int i=2;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<=m;k++)
{
dp[i][j][k]=dp[i-1][j][k];
if(s[i]=='j'&&s[i-1]=='z'&&j&&k)
dp[i][j][k]=max(dp[i][j][k],dp[i-2][j-1][k-1]+1);
else if(s[i]=='z'&&s[i-1]=='j')
dp[i][j][k]=max(dp[i][j][k],dp[i-2][j][k]+1);
else if(s[i]=='j'&&s[i-1]=='j'&&j)
dp[i][j][k]=max(dp[i][j][k],dp[i-2][j-1][k]+1);
else if(s[i]=='z'&&s[i-1]=='z'&&k)
dp[i][j][k]=max(dp[i][j][k],dp[i-2][j][k-1]+1);
if(j==k) ans=max(ans,dp[i][j][k]);
}
printf("%d
",ans);
return 0;
}
2018.9.5