「UVa 1471」Defense Lines - 贪心

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

UVa 链接

对于一个长度为 \(n (n \le 200000)\) 的序列，可删掉其中一段连续子序列。求删掉后序列的最长上升连续子序列。

解题思路

本题我们可以分解为求两段最长上升连续子序列，且满足前一个序列的最后一项小于后一个序列的第一项。我们可以先预处理出以 \(i\) 为开头的最长上升连续子序列的长度 \(f_i\) 和以 \(i\) 为结尾的最长上升子序列的长度 \(g_i\)。显然就可以得出答案为 \(\max\limits_{1 \le i \le n}\{ f_i + \max\limits_{1 \le j < i \wedge a_i > a_j} g_j \}\)。但这种做法时间复杂度为 \(O(n^2)\)，无法通过此题。于是我们需要考虑如何优化。

我们可以发现，对于两数 \(i\)、\(j\)，若 \(g_i \ge g_j \wedge a_i < a_j\)，则选 \(g_i\) 始终比选 \(g_j\) 更优，于是 \(g_j\) 不会被最优答案选取。我们可以用单调队列的思想，我们可以在对 \(f_i\) 进行遍历的时候维护一个 set 来存储可用的 \(g_j (j < i)\)。每次在 set 中插入 \(g_i\) 时，就删除所有满足 \(g_i \ge g_j \wedge a_i < a_j\) 条件的 \(g_j\)。查询时可用 lower_bound 查询满足小于 \(a_i\) 的最大的一个即可。这时复杂度就优化到了 \(O(n \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
#include <cstdio>
#include <set>

const int MAXN = 2e5;

void solve() {
    int n;
    static int a[MAXN + 1];

    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    static int f[MAXN + 1], g[MAXN + 1];
    g[1] = f[n] = 1;
    for (int i = n - 1; i >= 1; i--) {
        if (a[i] < a[i + 1]) f[i] = f[i + 1] + 1;
        else f[i] = 1;
    }
    for (int i = 2; i <= n; i++) {
        if (a[i - 1] < a[i]) g[i] = g[i - 1] + 1;
        else g[i] = 1;
    }

    int ans = 1;
    static std::set< std::pair<int, int> > s;
    s.clear();
    s.insert(std::make_pair(a[1], g[1]));
    for (int i = 2; i <= n; i++) {
        std::set< std::pair<int, int> >::iterator it = s.lower_bound(std::make_pair(a[i], 0));
        bool flag = true;

        if (it != s.begin()) {
            it--;
            ans = std::max(ans, (*it).second + f[i]);
            if (g[i] <= (*it).second) flag = false;
        }

        if (flag) {
            std::set< std::pair<int, int> >::iterator p = it;
            p++;
            while (p != s.end() && (*p).first > a[i] && (*p).second < g[i]) {
                it = p;
                p++;
                s.erase(it);
            }
            s.insert(std::make_pair(a[i], g[i]));
        }
    }

    printf("%d\n", ans);
}

int main() {
    int t;

    scanf("%d", &t);

    while (t--) solve();

    return 0;
}