题解 P1136 【迎接仪式】

· · 题解

首先看到这道题，贪心吗？不行，时间复杂度肯定是不够，我交了一下贪心30分，然后就想优化，搜索呢？ 剪枝一下40分是没问题的，仔细来看题，我们要做的是在k次操作中使得jz最多，考虑到做一次交换，由于两个位置放生变化，可能出现1~2个jz，而变换方式不能确定，和区间dp是不是很像有没有

所以 我们设dp[i][j][k]表示前i个字符，一共将j个j变成了z，将k个z变成了j，然后讨论一下当前的i与i-1是j还是z，对应转移方程 dp[i][j][k]=\begin{cases}dp[i-2][j][k]+1\\dp[i-2][j][k-1]+1\\dp[i-2][j-1][k]+1\\dp[i-2][j-1][k-1]+1\end{cases}//不要直接搞，要分情况讨论，每个方程对应不同情况

思路有了，那是不是马上解决这题，至于细节放在代码中了


#include<bits/stdc++.h>
#define ll long long

#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Rep(i,u) for(int i=head[u];i;i=Next[i])
#define clr(a) memset(a,0,sizeof a)
//没用的注释，忽略掉他们即可
using namespace std;

ll pp=1000000007;
ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
ll gcd(ll a,ll b){return (!b)?a:gcd(b,a%b);}
//一堆没有任何卵用的代码，再次忽略
inline int read()//快速读入，老快了，真的，我这人从来就不说假话
{
    int x=0;
    char ch=getchar();
    char c=ch;
    while(ch>'9'||ch<'0')c=ch,ch=getchar();
    while(ch<='9'&&ch>= '0')x=x*10+ch-'0',ch=getchar();
    if(c=='-')x=x*-1;
    return x;
}
void put(ll a)//快速输出，也是老快了，真的
{
    if(a<0)putchar('-'),a=-a;
    int top=0,q[20];
    while(a)q[++top]=a%10,a/=10;
    top=max(top,1);
    while(top--)putchar('0'+q[top+1]);
}

int n,m; 
char a[550];
const int inf=0x3f3f3f3f;//你写1e9我也没意见

int dp[550][110][110];

int main()
{
    ios::sync_with_stdio;//优化，可以去掉cin>>cout<<的缓存，但我好像并没有用这两个东西
    n=read();
    m=read();
    memset(dp,~0x3f,sizeof(dp));//附初值时要注意哈，得取个反
    scanf("%s",a+1);
    dp[0][0][0]=dp[1][0][0]=dp[1][a[1]=='j'][a[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时要考虑四种情况，不同情况下，去不同的最值
                dp[i][j][k]=dp[i-1][j][k];//初值附好
                if(a[i]=='z'&&a[i-1]=='j')
                    dp[i][j][k]=max(dp[i][j][k],dp[i-2][j][k]+1);
                if(k&&a[i]=='z'&&a[i-1]=='z')
                    dp[i][j][k]=max(dp[i][j][k],dp[i-2][j][k-1]+1);
                if(j&&a[i]=='j'&&a[i-1]=='j')
                    dp[i][j][k]=max(dp[i][j][k],dp[i-2][j-1][k]+1);
                if(j&&k&&a[i]=='j'&&a[i-1]=='z')
                    dp[i][j][k]=max(dp[i][j][k],dp[i-2][j-1][k-1]+1);
            }
        }
    }
    int ans=-inf;
    for(int i=0;i<=m;i++){
        ans=max(ans,dp[n][i][i]);//把每个到n的都枚举一遍，取最值
    }
    put(ans);
    return 0;
}