D1. Kirk and a Binary String (easy version)

01串找最长不降子序列

给定字符串s,要求生成一个等长字符串t，使得任意l到r位置的最长不降子序列长度一致

从后往前暴力枚举，枚举每个一替换成0后是否改变了l到r位置的最长不降子序列长度

01串的最长不降子序列，可以通过线性dp求解

dp i表示以i结尾的最长不降子序列长度

dp[0]=dp[0]+s[i]=='0';

dp[1]=max(dp[0],dp[1])+s[i]=='1';

#include<bits/stdc++.h>

using namespace std;

#define int long long

#define sc(x) scanf("%I64d",&(x));

typedef long long ll;

#define maxn 2005

#define INF 1e18

ll N;

ll val[][maxn];

ll dp[];

void LIS(string s,int st,int  val[])

{

    dp[]=dp[]=;

    for(int i=st;i<N;i++){

        if(s[i]==''){

            dp[]++;

        }else dp[]=max(dp[],dp[])+;

        val[i]=max(dp[],dp[]);

    }

}

signed main()

{

    string s,t;

    cin>>s;

    N=s.size();

    t=s;

    //int len=0;

    for(int i=N-; i>=;i--)

    {

        if(s[i]=='')

        {

            t[i]='';

            LIS(s,i,val[]);

            LIS(t,i,val[]);

            for(int j=i;j<N;j++){

                if(val[][j]!=val[][j]){

                    t[i]='';

                    break;

                }

            }

        }

    }

    cout<<t<<'\n';

}

下面这个大概思路是从后往前枚举，后面的0个数比1个数小时，可以删当前位置1

#include<bits/stdc++.h>

using namespace std;

#define int long long

#define sc(x) scanf("%I64d",&(x));

typedef long long ll;

#define maxn 2005

#define INF 1e18

ll N;

ll val[][maxn];

ll dp[];

void LIS(string s,int st,int  val[])

{

    dp[]=dp[]=;

    for(int i=st;i<N;i++){

        if(s[i]==''){

            dp[]++;

        }else dp[]=max(dp[],dp[])+;

        val[i]=max(dp[],dp[]);

    }

}

signed main()

{

    string s,t;

    cin>>s;

    N=s.size();

    t=s;

    int cnt=;

    for(int i=N-; i>=;i--)

    {

       if(s[i]==''){

         cnt++;

       }else if(cnt==&&s[i]==''){

           t[i]='';

       }else cnt--;

    }

    cout<<t<<'\n';

}

巴特西

D1. Kirk and a Binary String (easy version)

最新文章

热门文章