有长度为n的由数字1或2构成的序列,请你选择一个区间并将这个区间上的数字左右翻转,比如序列12112,翻转区间[3,5]后变成了12211.
只能翻转1个区间,使得翻转后序列的最长单调不减子序列长度最长.求出这个最大值.
子序列是指从原序列中选择一些元素不改变顺序地排列而成的新序列.
n<=3e5
题目链接(SEUOJ)
题目链接(CF)
解法
我们考虑按照最优解翻转之后得到的"最长单调不减子序列"是什么样的.它一定是形如1111111或222222或111111 222222.然后我们考虑子序列中的这些元素在翻转之前的相对位置是怎样的.前两种情况翻转之前也是它本身那个样子,第三种对翻转区间分类讨论:111[11 22]222或[11111 22]222或111[11 22222]或[11111 22222]或不翻转,只有这5种情况,它们对应的原序列形如111[22 11]222和[22 11111]222和111[22222 11]和[22222 11111]以及11111 22222(不翻转).
我们将所有这些情况所对应的原序列中元素的相对位置情况列出,其类型有:1\2\1212\212\121\21\12.所有这些类型都可以统一成1212,只不过这4个位置可能有为空的.
接下来只需要使用动态规划方法求出整个序列中形如11111 22222 111111 22222的最长子序列(其中连续的1或2可能是0个)就是答案了.
#include<iostream>
using namespace std;
int T,n,d[4];
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
d[0]=d[1]=d[2]=d[3]=0;
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
d[0]+=(x==1);
d[1]= x==1 ? max(d[0],d[1]) : d[1]+1;
d[2]= x==1 ? d[2]+1 : max(d[1],d[2]);
d[3]= x==1 ? max(d[2],d[3]) : d[3]+1;
}
printf("%d\n",d[3]);
}
}
