D2. Kirk and a Binary String (hard version)

[学习博客]来自 https://blog.csdn.net/qcwlmqy/article/details/99973051

我觉得有用的就是下面截图的这个部分。

因为你只需要考虑10递减的左右部分最长不递减的长度是不变的就可以了。那么我先从后面dp一下，求出后缀的每个位置的最长不递减序列长度（从后面好转移）

又因为上图说分成了若干个01串，前导为0，后导为1的串。。

整体考虑最长不递减长度不变那么区间最长不递减长度也就保证了不变。。

接着从s的后面开始新的dp，看当前1变为0时新的dp值（最长不递减长度）是否有变化，若没有说明当前位置可以变为0。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
char s[N],t[N];
int dp[N][2],newdp[N][2];
int main()
{
	cin>>s+1;
	int n=strlen(s+1);
	for(int i=n;i>=1;--i)
    {
        if(s[i]=='1')
        {
            dp[i][1]=dp[i+1][1]+1;
            dp[i][0]=dp[i+1][0];
        }
        else{
            dp[i][0]=max(dp[i+1][1],dp[i+1][0])+1;
            dp[i][1]=dp[i+1][1];
        }
    }
    /*for(int i=1;i<=n;++i)
    {
        printf("1:%d ",dp[i][1]);
        printf("0:%d\n",dp[i][0]);
    }*/
    for(int i=n;i>=1;--i)
    {
        if(s[i]=='0')
        {
            t[i]='0';
            newdp[i][0]=max(newdp[i+1][1],newdp[i+1][0])+1;
            newdp[i][1]=newdp[i+1][1];
        }
        else{
            int tmp=max(newdp[i+1][1],newdp[i+1][0])+1;
            //printf("tmp:%d dp[i][0]:%d\n",tmp,dp[i][0]);
            if(tmp==dp[i][1])
            {
                t[i]='0';
                newdp[i][0]=tmp;
                newdp[i][1]=newdp[i+1][1];
            }
            else{
                t[i]='1';
                newdp[i][1]=newdp[i+1][1]+1;
                newdp[i][0]=newdp[i+1][0];
            }
        }
    }
    for(int i=1;i<=n;++i) printf("%c",t[i]);

}