最长不降子序列
题面
小 W 有一个长度为 \(n\) 的序列 \(a_1, a_2 ...a_n\) ，且 \(a_i\) 的取值都为 1 或 2
现在，你可以任意选择该序列的一个区间进行翻转操作，但你只能翻转一次。
小 W 希望执行操作之后，整个序列的最长不下降子序列长度最大。请你求出这个最大值。
\(1 \le n \le 10^6\)
题解
这道题正解比较简单，考场上没有想到比较巧妙的思路，只能暴力dp，分数还好是拿到了，但是两个小时也过去了
暴力dp的思路就不说了，赛后看了看发现好像有点问题
假如我们不能翻转，那么最长不降子序列答案应该形如 \(111 ... 222 ...\)
如果能够翻转一次，那么答案应该形如 \(111 ... 222 ... 111 ... 222 ...\)
只要翻转中间的 $222 ... 111 ... $ 这一段即可转化为一个最长不降子序列
所以我们可以考虑每个点在哪一段，然后分别转移
设 \(f(i,1/2/3/4)\) 表示到第 \(i\) 个点，且第 \(i\) 个点在 \(1/2/3/4\) 段的最长不降子序列长度
转移
- \(f(i,1) = f(i - 1, 1) + [a_i =1]\)
- \(f(i,2) = max\{ f(i - 1, 2) ,f(i - 1, 1) \} + [a_i = 2]\)
- \(f(i,3) = max\{f(i - 1, 3), f(i - 1, 2) \} + [a_i = 1]\)
- \(f(i,4) = max \{f(i - 1, 4) , f(i - 1, 3)\} + [a_i = 2]\)
code
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>using namespace std;const int N = 1e6 + 10;int a[N], n;
int f[N][5];int main () {// freopen ("sequence.in", "r", stdin);// freopen ("sequence.out", "w", stdout);cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];for (int i = 1; i <= n; i++) {for (int j = 1; j <= 4; j++) {f[i][j] = max (f[i - 1][j - 1], f[i - 1][j]) + ((a[i] & 1) == (j & 1));}}cout << max ({f[n][1], f[n][2], f[n][3], f[n][4]}) << endl;return 0;
}