题解 P1136 【迎接仪式】

· · 题解

来Dew的博客观看？

楼上O(n^2m)做法不是很懂

但O(nm^2)的做法很神啊

看起来就是地痞，考虑一下如何把状态都给丢进去

因为一次涉及两个地方的位置，所以我们很难把这样的状态准确表示。

我们可以考虑先找一些特殊的突破点或者显然成立的贪心性质

说到特殊，这个序列的字符集只有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]);

格外注意一下答案更新的地方，相等时更新代表什么，其实就是代表匹配上去了，这些东西都在互有交换，但现在交换次数一样了，所以我们可以更新答案

值得一提的是，我们其实并没有单以位置划分状态，可以注意到，匹配的位置是前后都有的，我们是把位置和交换的状态放在一起，才做到了无后效性

个人拙见，如有错误，烦请提出