CF933A A Twisty Movement

发表于2020-08-12更新于2023-09-15字数统计513阅读时长4分

A Twisty Movement

Solution

由于 aia_i 的取值只有两种，那么某不下降子序列对应的翻转前的子序列一定由 [111...1][222...2][111...1][222...2][111...1][222...2][111...1][222...2] 这样的四段构成(每一段可以为空，但不全为空)。其中，第二段和第三段属于被翻转区间 [l,r][l,r]，这样翻转后第二段和第三段交换，于是得到形如 [111...1][222...2][111...1][222...2] 的不下降子序列(同样的，每一段可以为空，但不全为空)。对所有这样的子序列长度取最大值就是答案。

具体的，设当前位置为 ii，只需求 ii 之前形如 [111...1][222...2][111...1][222...2] 的最长子序列和 ii 之后形如 [111...1][222...2][111...1][222...2] 的最长子序列，即求 1→i1 \to i 的最长不下降子序列以及 n→i+1n \to i+1 的最长不上升子序列。分别从前往后、从后往前扫一遍用 DPDP 维护序列长度最大值即可。

时空复杂度 O(n)O(n)。

Code

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
35
36
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 2005;
int n, ans, a[MAXN];
int pre[MAXN][2], pos[MAXN][2];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        if (a[i] == 2) {
            pre[i][2] = max(pre[i - 1][2], pre[i - 1][1]) + 1;
            pre[i][1] = pre[i - 1][1];
        } else {
            pre[i][2] = pre[i - 1][2];
            pre[i][1] = pre[i - 1][1] + 1;
        }
    }
    for (int i = n; i; i--) {
        if (a[i] == 2) {
            pos[i][2] = pos[i + 1][2] + 1;
            pos[i][1] = pos[i + 1][1];
        } else {
            pos[i][2] = pos[i + 1][2];
            pos[i][1] = max(pos[i + 1][1], pos[i + 1][2]) + 1;
        }
    }
    for (int i = 1; i <= n; i++)
        ans = max(
            ans, max(pre[i][1], pre[i][2]) + max(pos[i + 1][1], pos[i + 1][2]));
    cout << ans;
    return 0;
}