P3928 一道简单题

Posted on Edited on In

题目大意：yhm拿到一个 3×n 的数组，要在每一列选一个数（或者不选）。满足以下条件：（1）如果在第一行选，那它必须大于等于上一个数（2）如果在第二行选，那么必须小于等于上一个数（3）如果在第三行选，对于连续的一段在第三行选的数，必须满足方向相同（都小于等于上一个数或者都大于等于上一个数）

显然可以搞出四个状态，然后n方转移

但是这个是最大值，所以可以用树状数组或者线段树优化成\(n\times log n\)

但是优化我不会，留坑待填

代码如下：

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#define int long long
using namespace std;

const int N = 1e5 + 66;

int n, m, res;
int a[6][N], f[N][6];
int b[N * 3], tree[6][N * 3];

#define lowbit(x) (x & (-x))

inline void chenge(int k, int x, int val)
{
    for (; x <= m; x += lowbit(x)) tree[k][x] = max(tree[k][x], val);
}

inline int query(int k, int x)
{
    int ret = 0;
    for (; x; x -= lowbit(x)) ret = max(ret, tree[k][x]);
    return ret;
}

signed main()
{
    n = read();

    for (int i = 1; i <= 3; ++ i)
    {
        for (int j = 1; j <= n; ++ j)
        {
            b[(i - 1) * n + j] = a[i][j] = read();
        }
    }

    sort(b + 1, b + 1 + n * 3);

    m = unique(b + 1, b + 1 + n * 3) - b - 1;

    for (int i = 1; i <= 3; ++ i)
    {
        for (int j = 1; j <= n; ++ j)
        {
            a[i][j] = lower_bound(b + 1, b + 1 + m, a[i][j]) - b;
        }
    }

    for (int i = 1; i <= n; ++ i)
    {
        {
            f[i][0] = query(0, a[1][i]) + 1;
            f[i][1] = query(1, m - a[2][i] + 1) + 1;
            f[i][2] = query(2, a[3][i]) + 1;
            f[i][3] = query(3, m - a[3][i] + 1) + 1;
        }

        {
            chenge(0, a[1][i], f[i][0]);
            chenge(0, a[2][i], f[i][1]);
            chenge(0, a[3][i], max(f[i][2], f[i][3]));
            chenge(1, m - a[1][i] + 1, f[i][0]);
            chenge(1, m - a[2][i] + 1, f[i][1]);
            chenge(1, m - a[3][i] + 1, max(f[i][2], f[i][3]));
            chenge(2, a[1][i], f[i][0]);
            chenge(2, a[2][i], f[i][1]);
            chenge(2, a[3][i], f[i][2]);
            chenge(3, m - a[1][i] + 1, f[i][0]);
            chenge(3, m - a[2][i] + 1, f[i][1]);
            chenge(3, m - a[3][i] + 1, f[i][3]);
        }
        res = max(res, max(max(f[i][0], f[i][1]), max(f[i][2], f[i][3])));
    }

    put(res);
    return 0;
}