题意
给出一个只含有1和2的序列，有n个元素，可以选择一段区间进行翻转操作，求再反转后的最大非递减子序列的长度
分析
太菜了只想出了N^2的做法。
序列只有1和2，那么每个非递减子序列都会有一个分界点，在分界点前是1以后是2。观察可以发现，只有当翻转的区间包含这个分界点的时候，这个分界点的非递减子序列的长度才会发生变化。定义dp[i][j]为反转区间i,j，且分界点在区间i,j的最长非递减子序列的长度。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=+;
int n;
int a[maxn];
int sum1[maxn],sum2[maxn];
int dp[maxn][maxn];
int main(){
scanf("%d",&n);
sum1[]=sum1[]=;
for(int i=;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]==){sum1[i]=sum1[i-]+;sum2[i]=sum2[i-];}
if(a[i]==){sum2[i]=sum2[i-]+;sum1[i]=sum1[i-];}
}
int ans=;
for(int i=;i<=n;i++)ans=max(ans,sum1[i]+sum2[n]-sum2[i]);
for(int i=;i<=n;i++)
dp[i][i]=sum1[i]+sum2[n]-sum2[i];
for(int len=;len<=n;len++){
for(int i=;i<=n-len+;i++){
int j=i+len-;
if(a[j]==&&a[i]==){
if(len>)dp[i][j]=dp[i+][j-]-;
else if(len<=)dp[i][j]=dp[i][j-]-;
}
else if(a[j]==&&a[i]==){
if(len>)dp[i][j]=dp[i+][j-]+;
else if(len<=)dp[i][j]=dp[i][j-]+;
}
else if(a[i]==a[j]){
if(len<=)dp[i][j]=dp[i][j-];
else
dp[i][j]=dp[i+][j-];
}
dp[i][j]=max(dp[i][j],max(sum1[j]+sum2[n]-sum2[j],sum1[i-]+sum2[n]-sum2[i-]+(a[j]==)));
}
}
for(int i=;i<=n;i++){
for(int j=i;j<=n;j++){
// cout<<i<<"---->"<<j<<" "<<dp[i][j]<<endl;
ans=max(ans,dp[i][j]);
}
}
printf("%d",ans);
return ;
}
这个题官方题解给出了O（n）的做法orzzzz