dp的思想。
$因为是子序列,所以可以不连续。$
$那么最后子序列的种类为以下几种:$
$(1)全为1:即111111 (在原序列中为1···1···1···1 (····代表>=0个1))$
$(2)全为2:即22222 (在原序列中为2···2··2····2 ( ·····代表>=0个2)) $
$(3)有1有2:由111 222 111 222翻转中间的222 111得到的111122222 (在原序列中11··22··11··22 $ $·····代表>=0个上一个点)$
$注:222211一定不可能,因为已经被2222包含$
$上述的’.’代表>=0个上一个点$
$那么这里定义四种状态长度(注:下面连续的1或2的个数不限):$
$状态1:s1表示序列全是1111 的长度:即11111$
$状态2:s2表示以2结尾且如果前面有数的话数只能是1 的长度:即1111222 (注:可以没有1)$
$状态3:s3表示以1结尾的长度且前面有数的话只能是22或1122 的长度:即111222111 $
$(注:可以没有前面的1或没有前面的111222)$
$状态4:s4表示以2结尾的长度且前面有数的话只能是11或1122或1122211 的长度:即112211122 $
$(注:可以没有前面的11或1122或112211)$
$那么只需要记录四种状态每个的最大值,最后取最值即可。$
$因为状态3包含状态1,状态4包含状态2,所以最后只需要对s3,s4求最值即可。$
$状态计算:从前往后扫$
$ 1、 如果是1,则s1++; 如果是2,s1不会更新.$
$2、 如果是2,则s2可以由s1转移而来即s1+1,或者由自己转移而来即s2+1 $
$即如果是2, s2=max(s1+1,s2+1); 如果是1,s2不会更新。$
$3、 如果是1,则s3可以由s2转移而来即s2+1(s3的许多状态其实已经被s2包含了),或者由自己转移而来即s3+1$
$即如果是1, s3=max(s3+1,s2+1); 如果是2,s3不会更新。$
$4、 如果是2,则s4可以由s3转移而来即s3+1(s4的许多状态其实已经被s3包含了),或者由自己转移而来即s4+1$
$即如果是2,则s4=max(s3+1,s4+1);如果是1,s4不会更新。$
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=200010;
int n;
int s1,s2,s3,s4;
int main()
{
scanf("%d",&n);
while(n--)
{
int x;
cin>>x;
if(x==1)
{
s1++;
s3=max(s2+1,s3+1);
}
else
{
s2=max(s1+1,s2+1);
s4=max(s3+1,s4+1);
}
}
cout<<max(max(s1,s2),max(s3,s4));
return 0;
}
其实就是一个 DP 拉 qwq