CF1204D2 Kirk and a Binary String (hard version) 题解

分析

先来分析 \(01\) 串的最长不下降子序列。全是 \(0\) 显然是不下降的，如果中间出现一个 \(1\)，为了维护不下降的性质，后面就只能全是 \(1\)。一句话概括一下，\(0\) 后面能跟 \(0,1\)，\(1\) 后面只能跟 \(1\)。

现在来分析这道题。显然有一种 \(\mathcal O(n^2)\) 的做法。从后往前遍历，如果这一位是 \(1\)，就先改成 \(0\)，然后用线性 dp 来求他们最长不下降子序列，看有没有改变。具体实现可以用 \(dp[i]\) 表示以 \(i\) 结尾的最长不下降子序列的长度，代码就不放了。

考虑 \(\mathcal O(n)\) 做法。还是得从后往前遍历，但是我们发现，把一位从 \(1\) 改成 \(0\) 会影响最长不下降子序列长度时，当且仅当这以为后面的 \(0\) 的个数比 \(1\) 的个数大。因为当你把一个 \(1\) 改成 \(0\) 时，这个 \(0\) 就可以和它后面的 \(0,1\) 都构成不下降子序列，而原来的 \(1\) 仅仅只能和后面的 \(1\) 来构成。只有后面的 \(1\) 的个数大于等于 \(0\) 的个数时，才不会对最长不下降子序列的长度造成影响。

\(\mathcal O(n)\) 代码

#include <bits/stdc++.h>
using namespace std;
namespace Raiden
{
    signed work()
    {
        string s;
        cin>>s;
        int n=s.size();
        int ans=0;
        for(int i=n-1;i>=0;i--)
        {
            if(s[i]=='0')
            {
                ans++;
            }
            else if(s[i]=='1'&&ans==0)
            {
                s[i]='0';
            }
            else
            {
                ans--;
            }
        }
        cout<<s<<endl;
        return 0;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return Raiden::work();
}