题解 P1136 【迎接仪式】

· · 题解

很容易看出来就是一个dp，

首先很容易想到一种设法：设dp[i][k]表示前i个字符，使用了k次交换后很获得的最多jz串数。

然后我们枚举最后一次交换的位置，即枚举一个j，然后交换i与j，用dp[j][k-1]+1去更新dp[i][k]。

效率大概是O(n^2*m)。

然后我们再仔细考虑一下，其实每次交换就是将一个j变成z，一个z变成j，那么我们就可以有另外一种方法：

设dp[i][j][k]表示前i个字符，一共将j个j变成了z，将k个z变成了j，然后讨论一下当前的i与i-1是j还是z，对应转移一下就好了。

这个方法不太好想，但是写起来复杂度低了很多。效率大概是O(n*m^2)

参考代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=501;
const int M=101;
template<class T>void ChkMax(T &a,T b){a=a<b?b:a;}
int dp[N][M][M],n,m;
char s[N];
int main(){
    scanf("%d%d",&n,&m);
    scanf("%s",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]=='z' && s[i-1]=='j')ChkMax(dp[i][j][k],dp[i-2][j][k]+1);
                if (k && s[i]=='z' && s[i-1]=='z')ChkMax(dp[i][j][k],dp[i-2][j][k-1]+1);
                if (j && s[i]=='j' && s[i-1]=='j')ChkMax(dp[i][j][k],dp[i-2][j-1][k]+1);
                if (j && k && s[i]=='j' && s[i-1]=='z')ChkMax(dp[i][j][k],dp[i-2][j-1][k-1]+1);
            }
    int ans=-INF;
    for (int i=0;i<=m;i++)ChkMax(ans,dp[n][i][i]);
    printf("%d",ans);
    return 0;
}