题目链接
思路分析：
每次看到dp的题目，就很慌，其实慌是正常的，因为这些题目都不正常。
看到题目后： 1. 尽可能地分析题目，转换题目意思，得到隐藏的解决策略。
2. 找dp状态，和状态转换关系，然后dp方程求解。
其实第一步是挺不简单的，需要有观察法的思想。
先分析，既然数组只有1 和 2，那么最终一定会有一个断点 11111****22222** 这样的，
假如正解的答案是[l.r],那么断点应该是在这个区间的，如果在前面或者后面，那么这个翻转就没有意义。就等于是l == r,自己翻转自己，那么解就对应了前述的特殊情况。
问题来了 ，可以等价于找[1 , l-1] 的1的个数 + [l,r]的最长下降子序列长度 + [r+1 , n]的2的个数 ,做一堆预处理即可，中间区间的最长下降子序列才是dp的核心，注意优化哦!
#include<bits/stdc++.h>
using namespace std;
int dp[2005][2005],pre[2005],ord[2005],ans = 0;
int main(){int n,a[2005];scanf("%d",&n);for(int i = 1;i<=n;i++) scanf("%d",&a[i]);//预处理 l r 的 最长不上升长度memset(dp,0,sizeof(dp)); memset(pre,0,sizeof(pre));memset(ord,0,sizeof(ord));int cnt = 0;for(int i = 1;i<=n;i++){if(a[i] == 1) cnt++;pre[i+1] = cnt;}cnt = 0;for(int i = n;i>=1;i--){if(a[i] == 2) cnt++;ord[i-1] = cnt;}for(int i = 1;i<=n;i++){int M1 = 0,M2 = 0;for(int j = i;j<=n;j++){if(a[j] == 1) dp[i][j] = max(M1,M2) + 1,M1 = max(M1,dp[i][j]);else dp[i][j] = M2 + 1,M2 = max(M2,dp[i][j]);}}for(int i = 1;i<=n;i++)for(int j = i;j<=n;j++)ans = max(ans,pre[i] + ord[j] + dp[i][j]);printf("%d",ans);
}