题目描述：
给定一个长度为 $ n $ 的序列，其中只包含数字 $ 1 $ 和 $ 2 $ 。选择一个区间 $ [l, r] $ 将元素翻转，使得到的序列的最长非递减子序列的长度最长。输出长度。
数据范围：
$ 1\le n \le 10^6 $
题解：
因为只有 $ 1 $ 和 $ 2 $ ，所以这就是突破口。翻转的话一定是翻转 $ 22222211111 $ 这种序列。翻转前的序列为 $ 111222221111 $ 或 $ 11122221111112222 $ 或 $ 22222211111122222 $ 。考虑使用 $ dp $ 转移。假设 $ a1 $ 表示类似 $ 111 $ 的全 $ 1 $ 序列，使用 $ a12 $ 表示类似 $ 111222 $ 的序列，使用 $ a121 $ 表示类似 $ 112211 $ 的序列，使用 $ a1212 $ 表示类似 $ 11222111122 $ 的序列
那么 $ a1 $ 可以转移到 $ a12 $ ， $ a12 $ 转移到 $ a121 $ ， $ a121 $ 转移到 $ a1212 $ ，答案就是 $ \max(a121, a1212) $
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 4e5 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
read(n);
int a1 = 0, a12 = 0, a121 = 0, a1212 = 0;
for (int i = 1, x; i <= n; i++)
{
read(x);
if (x == 1)
{
a1 += 1;
a121 = max(a121 + 1, a12 + 1);
}
else
{
a12 = max(a12 + 1, a1 + 1);
a1212 = max(a1212 + 1, a121 + 1);
}
}
printf("%d\n", max(a121, a1212));
return 0;
}
|