题意翻译
给定一个序列 A，你可以翻转其中的一个区间内的数，求翻转后的序列的最长不下降子序列的长度。（∣A∣≤2000,1≤ai≤2|A|\le 2000,1\le a_i \le 2∣A∣≤2000,1≤ai≤2 ）
感谢@touristWang 提供的翻译
题目描述
A dragon symbolizes wisdom, power and wealth. On Lunar New Year's Day, people model a dragon with bamboo strips and clothes, raise them with rods, and hold the rods high and low to resemble a flying dragon.
A performer holding the rod low is represented by a 1 1 1 , while one holding it high is represented by a 2 2 2 . Thus, the line of performers can be represented by a sequence a1,a2,...,an a_{1},a_{2},...,a_{n} a1,a2,...,an .
Little Tommy is among them. He would like to choose an interval [l,r] [l,r] [l,r] ( 1<=l<=r<=n 1<=l<=r<=n 1<=l<=r<=n ), then reverse al,al+1,...,ar a_{l},a_{l+1},...,a_{r} al,al+1,...,ar so that the length of the longest non-decreasing subsequence of the new sequence is maximum.
A non-decreasing subsequence is a sequence of indices p1,p2,...,pk p_{1},p_{2},...,p_{k} p1,p2,...,pk , such that p1<p2<...<pk p_{1}<p_{2}<...<p_{k} p1<p2<...<pk and ap1<=ap2<=...<=apk a_{p1}<=a_{p2}<=...<=a_{pk} ap1<=ap2<=...<=apk . The length of the subsequence is k k k .
输入输出格式
输入格式：The first line contains an integer n n n (1<=n<=2000) (1<=n<=2000) (1<=n<=2000) , denoting the length of the original sequence.
The second line contains n n n space-separated integers, describing the original sequence a1,a2,...,an a_{1},a_{2},...,a_{n} a1,a2,...,an (1<=ai<=2,i=1,2,...,n) (1<=a_{i}<=2,i=1,2,...,n) (1<=ai<=2,i=1,2,...,n) .
输出格式：Print a single integer, which means the maximum possible length of the longest non-decreasing subsequence of the new sequence.
输入输出样例
41 2 1 2
4
101 1 2 2 2 1 1 2 2 1
9
说明
In the first example, after reversing [2,3], the array will become [1,1,2,2] , where the length of the longest non-decreasing subsequence is 4 .
In the second example, after reversing [3,7] , the array will become [1,1,1,1,2,2,2,2,2,1] , where the length of the longest non-decreasing subsequence is 9 .
Solution：
本题思维题。
因为$a_i$只有$1,2$两种可能，于是我们可以确定的是答案一定是：$[1,1,1,…]\;[2,2,2…]\;[1,1,1…]\;[2,2,2…]$这样的四段子序列（每一段都允许为空），使得第二、三段所在区间翻转得到答案（不翻转可以理解为二、三段为空序列）。
解法一：
我们可以从左往右做前缀和$ct1[i]$表示$[1,i]$出现的$1$的个数，同理做出后缀和$ct2[i]$表示$[i,n]$出现的$2$的个数。然后我们枚举断点$k,k\in[1,n+1]$（即二、三段的分界点），设一、二段的分界点为$p,p\in[1,k]$，三、四段的分界点为$q,q\in[k,n+1]$，那么显然答案为$(ct1[p-1])+(ct2[p]-ct2[k])+(ct1[q-1]-ct1[k])+(ct2[q])$，式子中括号括起来的为一段，这个式子可以化为$(ct1[p-1]+ct2[p]+ct1[q-1]+ct2[q])-(ct1[k]+ct2[k]),p\in[1,k],q\in[k,n+1]$，注意到对于一个确定的$k$，我们要最大化前面括号的式子，而前者可以用线段树维护下$ct1[i-1]+ct2[i]$，那么只用枚举$k$，再两次区间最大值查询，更新答案就好了。
时间复杂度$O(n\log n)$。
代码：
/*Code by 520 -- 10.20*/#include#define il inline#define ll long long#define RE register#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)#define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1using namespace std;const int N=1000005;int n,ans,ct1[N],ct2[N],a[N],ppx[N];struct SGT{ int maxn[N<<2]; il void pushup(int rt){maxn[rt]=max(maxn[rt<<1],maxn[rt<<1|1]);} void build(int l,int r,int rt){ if(l==r) {maxn[rt]=ppx[l];return;} int m=l+r>>1; build(lson),build(rson); pushup(rt); } int query(int L,int R,int l,int r,int rt){ if(L<=l&&R>=r) return maxn[rt]; int m=l+r>>1,res=0; if(L<=m) res=max(res,query(L,R,lson)); if(R>m) res=max(res,query(L,R,rson)); return res; }}T;int main(){ scanf("%d",&n); int t1,t2; For(i,1,n) scanf("%d",a+i),ct1[i]=ct1[i-1]+(a[i]==1); Bor(i,1,n) ct2[i]=ct2[i+1]+(a[i]==2); For(i,1,n+1) ppx[i]=ct1[i-1]+ct2[i]; T.build(1,n+1,1); For(k,1,n+1) { t1=T.query(1,k,1,n+1,1),t2=T.query(k,n+1,1,n+1,1); ans=max(ans,t1+t2-ct1[k-1]-ct2[k]); } cout<
解法二：
我们显然（事实上考试只想出了解法一）可以用DP来维护每段的最大值。
定义状态$f[i][1]$表示前$i$个数中前一段的答案，$f[i][2]$表示前$i$个数中前两段的答案，$f[i][3]$表示前$i$个数中前三段的答案，$f[i][4]$表示前$i$个数中前四段的答案。
那么不难得到状态转移方程：
$f[i][1]=f[i-1][1]+(a_i==1)$
$f[i][2]=max(f[i-1][1],f[i-1][2]+(a_i==2))$
$f[i][3]=max(f[i-1][2],f[i-1][3]+(a_i==1))$
$f[i][4]=max(f[i-1][3],f[i-1][4]+(a_i==2))$
显然第一维是可以压掉的,时间复杂度$O(n)$。
代码：
/*Code by 520 -- 10.20*/#include#define RE register#define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)using namespace std;int n,x,f[5];int main(){ scanf("%d",&n); For(i,1,n) scanf("%d",&x), f[1]+=(x==1), f[2]=max(f[1],f[2]+(x==2)), f[3]=max(f[2],f[3]+(x==1)), f[4]=max(f[3],f[4]+(x==2)); cout<