思路
假设我们最后的非递减的子序列在变化前为 11111…22222....1111…22222,总共4段(四种状态)
我们设s1,s2,s3,s4,代表每一段的末尾
考虑线性dp的做法
因此我们只需要维护好4个不同的状态的最大值,最后就能求出最大值。
讨论每一段(状态)的增加(转移)
1. s1增加的时候很好理解,即s1=s1+1
2. s2从两种状态转移,第一种是在s1的末尾添加一个2,代表转化到s2状态中,第二种是在s2的末尾继续增加长度
3. s3从两种状态转移,第一种是在s2的末尾添加一个1,代表转化到s3状态中,第二种是在s3的末尾继续增加长度
4. s4从两种状态转移,第一种是在s3的末尾添加一个2,代表转化到s4状态中,第二种是在s4的末尾继续增加长度
我们发现$s3>=s1, s4>=s2$ 因此答案就是$max(s3,s4)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
int s1 = 0, s2 = 0, s3 = 0, s4 = 0;
while (n--)
{
int x;
scanf("%d", &x);
if (x == 1)
{
s1 = s1 + 1;
s3 = max(s3 + 1, s2 + 1);
}
else
{
s2 = max(s1 + 1, s2 + 1);
s4 = max(s3 + 1, s4 + 1);
}
}
printf("%d\n", max(s3, s4));
return 0;
}