题解

UVA1471 Defense Lines

题目描述

给定一个长度为 $n(n≤200000)$的序列,你的任务是删除一个连续子序列,使得剩下的序列中有一个长度最大的连续递增子序列。例如,将序列$ \lbrace 5,3,4,9,2,8,6,7,1 \rbrace$中的 $ \lbrace 9,2,8 \rbrace $ 删除,得到的序列 $ \lbrace 5,3,4,6,7,1 \rbrace $ 中包含一个长度为 $4$ 的连续递增子序列 $ \lbrace 3,4,6,7 \rbrace $。序列中每个数均为不超过 $10^9$ 的正整数。

题目链接

UVA1471

题解

设 $pre_i $ 表示原序列中以第 $i$ 个数为结尾的最长连续递增子序列的长度,$suc$ 表示原序列中以第 $i$ 个数为开头的最长连续递增子序列的长度。
这两个数组扫一遍就可以求出来了。
因为求的是删除一段序列之后的最长连续递增子序列,所以不难想到答案一定是如下三种情况中的最优值

  • $\max(pre_i)$;
  • $\max(suc_i)$;
  • $\max(pre_i+suc_j)$,其中 $i < j$ 且 $a_i < a_j$

前两种情况求的时候就可以比较了。
第三种情况用树状数组维护后缀最大值,倒着扫一遍就可以求出来对于每个数拼起来的答案最大是多少了。

代码

#include <cstdio>
#include <climits>
#include <cstring>
#include <algorithm>
#include <cmath>
const int MAXN = 2e5 + 7;
int a[MAXN], pre[MAXN], suc[MAXN], s[MAXN];
int t[MAXN], end;
inline int lowbit(int x) {
    return x & (-x);
}
void change(int x, int delta) {
    for (int i = x; i; i -= lowbit(i)) {
        t[i] = std::max(t[i], delta);
    }
}
int query(int x) {
    int ret = 0;
    for (int i = x; i <= end; i += lowbit(i)) {
        ret = std::max(ret, t[i]);
    }
    return ret;
}
int main(int argc, char *argv[]) {
    int r;
    scanf("%d", &r);
    while (r--) {
        int n;
        memset(t, 0, sizeof t);
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
            s[i] = a[i];
        }
        std::sort(s + 1, s + n + 1);
        end = std::unique(s + 1, s + n + 1) - (s + 1);
        for (int i = 1; i <= n; i++) {
            a[i] = std::lower_bound(s + 1, s + end + 1, a[i]) - s;
        }
        pre[1] = 1;
        int ans = 0;
        for (int i = 2; i <= n; i++) {pre[i] = a[i - 1] < a[i] ? pre[i - 1] + 1 : 1; ans = std::max(ans, pre[i]); }
        suc[n] = 1;
        for (int i = n - 1; i; i--) {suc[i] = a[i] < a[i + 1] ? suc[i + 1] + 1 : 1; ans = std::max(ans, suc[i]);}
        for (int i = n; i; i--) {
            ans = std::max(ans, pre[i] + query(a[i] + 1));
            change(a[i], suc[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注