图片说明
图片说明

题意：
给出一个01字符串，输出一个字符串t，使得s和t的所有子串的非递减子序列长度相同，且0的个数最多

题解：
从后面往前面找结果，记录0的个数和1的个数
先考虑0：
0肯定不变，要保证以这个0为起点的子串的最长的非递减子序列的长度
下面考虑1：
如果子串的非递减子序列包含这个1，那么前面肯定都是1，那么如果变成0，那么是不影响结果的。
如果字串的非递减子序列不包含这个1，那么如果变成0，那么肯定会影响非递减子序列的长度
结果显而易见：
如果1的后面的1的个数>0的个数那么就可以将1变为0，否则就不能变。

代码:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    int l = s.length(),cnt = 0;
    for(int i=l-1;i>=0;i--)
    {
        if(s[i] == '0')
            cnt++;
        else{
            if(cnt)
                cnt--;
            else
                s[i] = '0';
        }
    }
    cout<<s<<endl;
    return 0;
}