本文共 1379 字，大约阅读时间需要 4 分钟。

[学习博客]来自 

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

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

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

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

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

AC代码：

#include
   
    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]);}
   

转载地址：https://ccsudeer.blog.csdn.net/article/details/100016128 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！