【链接】

【题意】

【题解】

因为只有1和2.

所以最后肯定是若干个1接着若干个2的情况。

即11...11222...222这样的。

1.首先考虑没有翻转的情况。

那么就直接枚举1和2的边界i在什么地方,即1..i全是1,i+1..n全是2.

只需统计某个范围里面1和2的个数就可以了。

然后取最大值就ok.

2.考虑有翻转的情况.

假设翻转的区间是[i..j]

我们最好先固定j然后让i从j递减到1这样变化.

这样的话我们可以利用[i+1,j]这一段得到的东西继续搞,不用每次都重新算.

(注意倒过来以后相当于j是开始位置

我们可以对于这段区间维护两个变量

int pre1max = 0,pre2max = 0;

他们俩分别表示[i..j]这一段倒过来以后,以1作为结尾的LIS的长度和以2作为结尾的LIS的长度.

然后遇到了1的话,pre1max=pre1max+1.(因为只能在前面的1后面再接一个1

如果遇到了2的话,pre2max=max(pre2max,pre1max)+1;(表示既能在2后面接一个2也能在1后面接一个2).

然后对于每一段的i..j求出来一个pre1max和pre2max之后,都

用"1到i-1里面1的个数"+pre2max+"j+1到n里面2的个数"来更新最大值

(注意这个翻转肯定只能包括上面说的1和2的边界处翻转才有效果,否则如果是在11111..11这一段或者在22222..22这一段翻转的话,显然不会影响答案.

(这种情况就相当于没有翻转的情况了.

【代码】

#include 
    
     using namespace std;const int N = 2000;int n;int a[N+10];int pre[N+10][3];int getsum(int p,int l,int r){    if (l==0) return pre[r][p];    if (l>r) return 0;    return pre[r][p]-pre[l-1][p];}int main(){    ios::sync_with_stdio(0),cin.tie(0);    cin >> n;    for (int i = 1;i <= n;i++) cin >> a[i];    for (int i = 1;i <=n;i++){        for (int j = 1;j <= 2;j++)            pre[i][j] = pre[i-1][j];        pre[i][a[i]]++;    }    int ans = 0+getsum(2,1,n);    for (int i = 1;i <= n;i++)        ans = max(ans,getsum(1,1,i)+getsum(2,i+1,n));    for (int j = n;j >= 1;j--){        int pre1max = 0,pre2max = 0;        if (a[j]==1) pre1max = 1;else pre2max = 1;        for (int i = j-1;i >= 1;i--){            if (a[i]==1){                pre1max++;            }else{                pre2max=max(pre2max,pre1max)+1;            }            ans = max(ans,getsum(1,1,i-1)+pre2max+getsum(2,j+1,n));        }    }    cout<
     
      <