问题 B: 子序列
时间限制: 1 Sec 内存限制: 128 MB

题目描述
小Z有一个01序列A=(A1,A2,A3,...,An)。他可以进行一次操作：选择一个区间L,R将其反转。
例如，对于序列A=(1,0,0,1,1)，当L=2,R=4时，原序列将变为(1,1,0,0,1)。
小Z希望：通过这一次反转操作，使得这个序列的最长不下降子序列的长度尽可能的大，并想让你输出这个最大值。
一个序列的不下降子序列定义为：对于一个序列(p1,p2,...,pk)满足1≤p1<p2<...<pk≤n(n≤819200)且Ap1≤Ap2≤...≤Apk。则序列(Ap1,Ap2,...,Apk)为不下降子序列，其中k为这个不下降子序列的长度。
输入
一行一个01字符串，表示序列A
输出
一行一个正整数，表示最长不下降子序列长度的最大值。
样例输入 Copy
00111001101
样例输出 Copy
10
提示
一种最优策略为：反转区间[3,7]，数列将变为(0,0,0,0,1,1,1,1,1,0,1) ，其最长不下降子序列的长度为10。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PLL;
typedef pair<int, int>PII;
typedef pair<double, double>PDD;
#define I_int ll
inline ll read()
{
    ll x = 0, f = 1;
    char ch = getchar();
    while(ch < ‘0‘ || ch > ‘9‘)
    {
        if(ch == ‘-‘)f = -1;
        ch = getchar();
    }
    while(ch >= ‘0‘ && ch <= ‘9‘)
    {
        x = x * 10 + ch - ‘0‘;
        ch = getchar();
    }
    return x * f;
}
 
inline void out(ll x){
    if (x < 0) x = ~x + 1, putchar(‘-‘);
    if (x > 9) out(x / 10);
    putchar(x % 10 + ‘0‘);
}
 
inline void write(ll x){
    if (x < 0) x = ~x + 1, putchar(‘-‘);
    if (x > 9) write(x / 10);
    putchar(x % 10 + ‘0‘);
}
 
#define read read()
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
ll ksm(ll a, ll b, ll p)
{
    ll res = 1;
    while(b)
    {
        if(b & 1)res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
 
const int maxn=1e6+100,maxm=1e5+10;
 
int dp[4];
 
int main(){
    string s;cin>>s;
    for(int i=0;s[i];i++){
        if(s[i]==‘0‘){
            dp[0]++;
            dp[2]=max(dp[2],dp[1])+1;
        }
        else{
            dp[1]=max(dp[0],dp[1])+1;
            dp[3]=max(dp[3],dp[2])+1;
        }
    }
     
    int res=dp[0];
    rep(i,1,3) res=max(res,dp[i]);
    write(res);
    return 0;
}
 
 
 
 
 

问题 B: 子序列