题目大意：
给出一组长度为n由整数1和2构成的数组a，有一种对数组a的操作，规定一个区间，在这个区间的元素逆序，该操作只能执行一次，要求你在执行一次该操作之后，使得数组a的最长不下降子序列的长度最长。
分析：
首先，最长不下降子序列这个序列是不用连续的，题目中也没出现“continuous”这类字样，所以题意看懂很要紧。其次，数组长度最大为2000，所以不可能用O(n^2)的方法求最长，必须用O(n*logn)。但是按照题目意思先逆序再求也会超时，所以可以这么思考，既然必须要逆序那个区间来达到最长，那么那段区间的逆序的最长不下降子序列必须要用到，因为数组是由1和2组成所以区间内的子序列必定是由若干个1后面加上若干个2或者若干个1或者若干个2这三种情况，那么求出该区间的最长不上升子序列的长度就相当于逆序之后的最长不下降子序列的长度，只要知道区间左边1的个数以及区间右边2的个数，三者相加就是逆序后数组a最长不下降子序列的长度。所以dp所有情况求出每次三者相加的最大值即是逆序之后的最大值。
题目链接：Codeforces Round #462 (Div. 2) C
代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N=2000+10; int a[N],b[N],n,b1[N],b2[N]; int main() { while(~scanf("%d",&n)){ int _max=1; memset(b1,0,sizeof(b1)); memset(b2,0,sizeof(b2)); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=1;i<=n;i++){ if(a[i]==1){ b1[i]=b1[i-1]+1; b2[i]=b2[i-1]; } else { b2[i]=b2[i-1]+1; b1[i]=b1[i-1]; } } for(int i=1;i<=n;i++){ int len =1 ; b[1]=-a[i]; _max=max(_max,b1[i-1]+b2[n]-b2[i]+1); for(int j=i+1;j<=n;j++){ if(-a[j]>=b[len]) b[++len]=-a[j]; else { int pos=upper_bound(b+1,b+len,-a[j])-b; b[pos]=-a[j]; } _max=max(_max,len+b1[i-1]+b2[n]-b2[j]); } } printf("%d\n",_max); } return 0; }