933A Twisty Movement

###问题描述
给定一个有1和2组成的序列，我们可以把其中的[i,j]进行一次翻转(当然也可以不翻转).求问经过翻转后的序列的最长不递减子序列长度。

Sample Input

4
1 2 1 2

10
1 1 2 2 2 1 1 2 2 1

Sample Output

4
9

Note

第一组翻转[2,3]
第二组翻转[3,7]

问题分析

因为只有1和2，假设我们翻转了[i,j]，它的最长不递减子序列就是区间前面1的数量 + [i,j]的下降子序列 + 区间后面2的数量.
我们只要预处理出1的前缀和，2的后缀和与[i,j]的最长下降子序列长度，就可以靠DP更新答案.

怎么求出每个[i,j]区间最长下降子序列长度呢？我们可以靠DP解决。

设
dp[i][j][0]是以2结尾的下降子序列长度，明显就是[i,j]内2的个数
dp[i][j][1]是以1结尾的下降子序列长度

可以得出状态转移方程

$dp[i][j][0] = dp[i][j-1][0] + (num[j] == 2)$
$dp[i][j][1] = max(dp[i][j-1][0] , dp[i][j-1][1]) + (num[j] == 1)$

区间[i,j]的最长下降子序列长度就是 $max(dp[i][j][0],dp[i][j][1])$

然后通过dp更新ans
$ans = max(ans,max(dp[i][j][0],dp[i][j][1]))$

代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 2000 + 10;
int num[maxn],pre[maxn],suf[maxn],dp[maxn][maxn][2];
/*dp[i][j][0]  表示区间内以2结尾的最长不上升子序列
  dp[i][j][1]   表示区间内以1结尾的最长不上升子序列*/

int main()
{
  int n,ans = 0;
  cin >> n;
  for(int i=1;i<=n;i++) cin >> num[i];
  for(int i=1;i<=n;i++) pre[i] = pre[i-1] + (num[i] == 1); //预处理1的前缀
  for(int i=n;i>=1;i--) suf[i] = suf[i+1] + (num[i] == 2); //预处理2的后缀
  for(int i=1;i<=n;i++)
  for(int j=i;j<=n;j++)
  {
    if(i==j)
    {
      dp[i][j][0] = (num[i] == 2);
      dp[i][j][1] = (num[i] == 1);
    }
    else
    {
      dp[i][j][0] = dp[i][j-1][0] + (num[j] == 2);
      dp[i][j][1] = max(dp[i][j-1][0],dp[i][j-1][1]) + (num[j] == 1);
    }
    ans = max(ans,pre[i-1] + max(dp[i][j][0],dp[i][j][1]) + suf[j+1]);
  }
  cout << ans << endl;
}