P1136 迎接仪式题解

· · 个人记录

先读题，这题显然是一道 DP 题；

于是，我们设计状态：

两串两串的扫，会发现: $ dp[i][j][k] $ 从 $ dp[i-1][j][k] $ 直接转移过来。 若交换的字符串为 "jz"： $ dp[i][j][k]=dp[i-2][j][k]+1

若交换的字符串为 "zz" ：

dp[i][j][k]=dp[i-2][j-1][k]+1

若交换的字符串为 "zj"：

dp[i][j][k]=dp[i-2][j-1][k-1]+1

若交换的字符串为 "jj"：

dp[i][j][k]=dp[i-2][j][k-1]+1

接下来就是预处理：

如果交换的次数如果大于 1 ，有可能会交换 i = 2 之前的字符串。

于是，我们把所有设为最小（负无穷）把前两位设为 0 ，

这样有效状态就会转移。

还有一点，循环中会越界，因此 j,k = 0 的情况要舍去。

注意乱开 long long 会 MLE 。

上代码！

#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 505
using namespace std;
int dp[N][160][160],n,kk,ans;
char s[N],zz='z',jj='j';
signed main(){
    scanf("%d%d",&n,&kk);
    scanf("%s",s+1);
    if(kk-1){
        memset(dp,-0x3f,sizeof(dp));
       dp[1][0][0]=dp[0][0][0]=0;
    }
    for(int i=2;i<=n;i++){
        for(int j=0;j<=kk;j++){
            for(int k=0;k<=kk;k++){
                dp[i][j][k]=dp[i-1][j][k];
                char a=s[i-1],b=s[i];
                if(a==jj&&b==zz)dp[i][j][k]=dp[i-2][j][k]+1;
                if(a==zz&&b==zz&&j)dp[i][j][k]=dp[i-2][j-1][k]+1;
                if(a==zz&&b==jj&&j&&k)dp[i][j][k]=dp[i-2][j-1][k-1]+1;
                if(a==jj&&b==jj&&k)dp[i][j][k]=dp[i-2][j][k-1]+1;
                if(j==k&&j&&k)ans=max(dp[i][j][k],ans);
            }
        }
    }
    printf("%d",ans);
    return 0;
}