稍微解释一下 yxc 老师的额思路
因为值只有 $1,2$,这大大简化了问题
首先我们贪心的考虑,一定翻转形如 $222\dots 111$ 这样的一段——因为这样可以使得增加 LIS 的长度
那么
对于一个 $1$ ,要么属于原本的正常上升的一段,要么属于要翻转的一段
对于一个 $2$ ,要么属于原本的正常上升的一段,要么属于要翻转的一段之后的
维护四个值,随便 DP 一下就可以了
注意到每个值的意义,是不会互相干扰的 :)
/*
* AcWing 3549, warm-up contest 1 C
* Author: Wu Wenhao
* Date: 2021/5/23
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int my_max(int a, int b, int c, int d) {
return max(max(max(a, b), c), d);
}
int main() {
int n;
scanf("%d", &n);
int dp1, dp2, dp3, dp4;
dp1 = dp2 = dp3 = dp4 = 0;
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
if (x == 1) {
++dp1;
dp3 = max(dp3 + 1, dp2 + 1);
}
else {
dp2 = max(dp2 + 1, dp1 + 1);
dp4 = max(dp4 + 1, dp3 + 1);
}
}
printf("%d\n", my_max(dp1, dp2, dp3, dp4));
return 0;
}