A. A Twisty Movement(翻转区间求最长不下降子序列)

https://codeforces.com/problemset/problem/933/A

题意翻译

给定一个序列 A，你可以翻转其中的一个区间内的数，求翻转后的序列的最长不下降子序列的长度。（|A|\le 2000,1\le a_i \le 2∣A∣≤2000,1≤ai​≤2 ）

感谢@touristWang 提供的翻译

输入输出样例

输入 #1复制

4
1 2 1 2

输出 #1复制

4

输入 #2复制

10
1 1 2 2 2 1 1 2 2 1

输出 #2复制

9

说明/提示

In the first example, after reversing [2,3][2,3] , the array will become [1,1,2,2][1,1,2,2] , where the length of the longest non-decreasing subsequence is 44 .

In the second example, after reversing [3,7][3,7] , the array will become [1,1,1,1,2,2,2,2,2,1][1,1,1,1,2,2,2,2,2,1] , where the length of the longest non-decreasing subsequence is 99 .

---

思路：n<=2e3.所以可以n^2暴力去想。

n^2可以枚举翻转的区间，dp[l][r][1],dp[l][r][2]分别代表l~r区间内以1为结尾或者以2为结尾的非递增子序列。

dp[l][r][1]=max(dp[l][r-1][1],dp[l][r-1][2])+(a[i]==1)  以1为结尾的非递增可以从2/1结尾的转移过来。

dp[l][r][2]=dp[l][r-1][2]+(a[i]==2);

剩下就处理前缀1和后缀2，最后在n^2枚举中处理ans最大值。

启发：

求解最长不下降子序列在数字只有常数个的时候可以枚举以哪个数字结尾来dp。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=2e3+100;
typedef long long LL;
LL dp[maxn][maxn][3];
LL a[maxn],pre[maxn],suf[maxn];
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  LL n;cin>>n;
  for(LL i=1;i<=n;i++) cin>>a[i];
  for(LL i=1;i<=n;i++) pre[i]=pre[i-1]+(a[i]==1);
  for(LL i=n;i>=1;i--) suf[i]=suf[i+1]+(a[i]==2);
  LL ans=0;
  for(LL l=1;l<=n;l++){
  	for(LL r=l;r<=n;r++){
  		dp[l][r][2]=dp[l][r-1][2]+(a[r]==2);
  		dp[l][r][1]=max(dp[l][r-1][1],dp[l][r-1][2])+(a[r]==1);
  		ans=max(ans,pre[l-1]+max(dp[l][r][1],dp[l][r][2])+suf[r+1]);
	}
  }
  cout<<ans<<endl;
return 0;
}

附上浅色调大佬的O（n）解法：

/*Code by 520 -- 10.20*/
#include<bits/stdc++.h>
#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<<f[4];
  return 0;
}