2119: 无尽递增 时间限制: 1 Sec 内存限制: 128 MB 提交: 71 解决: 11 [提交] [状态] [讨论版] [命题人:admin] 题目描述
有一个只包含1和2的序列，试翻转一个区间，使得结果中非递减子序列最长。输出翻转后数列中非递减子序列的最长长度。
输入
第一行为数据组数T，每组数据包含两行，第一行为序列的长度，第二行为n个数，表示数列中的数。(T <=6 && n <= 2e5)
输出
每组数据输出一行，表示答案。
样例输入
1 4 2 2 1 1
样例输出
4
转化题意后，其实就是找出最长的1111222211112222 即1…2…1…2的最长子序列 我们可以开dp【4】，分别表示以红色标出的值为结尾的最长子序列。 转移公式为：
#include<bits/stdc++.h> #define fi first #define se second #define log2(a) log(n)/log(2) #define show(a) cout<<a<<endl; #define show2(a,b) cout<<a<<" "<<b<<endl; #define show3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl; using namespace std; typedef long long ll; typedef pair<int, int> P; typedef pair<P, int> LP; const ll inf = 1e17 + 10; const int N = 2e5 + 10; const ll mod = 1e9+7; const int base=131; const double pi=acos(-1); map<string, int>ml; int t,n,m; int dp[10],a[N]; int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); memset(dp,0,sizeof dp); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) { dp[1]=max(dp[1],dp[1]+(a[i]==1)); dp[2]=max(dp[1],dp[2]+(a[i]==2)); dp[3]=max(dp[2],dp[3]+(a[i]==1)); dp[4]=max(dp[3],dp[4]+(a[i]==2)); } printf("%d\n",dp[4]); } }