[NOIP2013提高]花匠 题解

[NOIP2013提高]花匠 题解

题目地址:洛谷:P1970 花匠 – 洛谷 | 计算机科学教育新生态

题目描述

花匠栋栋种了一排花,每株花都有自己的高度。花儿越长越大,也越来越挤。栋栋决定把这排中的一部分花移走,将剩下的留在原地,使得剩下的花能有空间长大,同时,栋栋希望剩下的花排列得比较别致。
具体而言,栋栋的花的高度可以看成一列整数$h_1, h_2, \dots, h_n$。设当一部分花被移走后,剩下的花的高度依次为$g_1, g_2, \dots, g_n$,则栋栋希望下面两个条件中至少有一个满足:
条件A:对于所有$1 \leq i \leq m/2$,有$g_{2i} > g_{2i-1}$,同时对于所有的$1 \leq i \leq m/2$,有$g_{2i} > g_{2i+1}$
条件B:对于所有$1 \leq i \leq m/2$,有$g_{2i} < g_{2i-1}$,同时对于所有的$1 \leq i \leq m/2$,有$g_{2i} < g_{2i+1}$
注意上面两个条件在$m=1$时同时满足,当$m>1$时最多有一个能满足。
请问,栋栋最多能将多少株花留在原地。

一句话题意

给你一个正整数序列,找出其中最长的摆动子序列。

输入输出格式

输入格式:
第一行包含一个整数n,表示开始时花的株数。
第二行包含n个整数,依次为$h_1, h_2, \dots, h_n$,表示每株花的高度。

输出格式:
一个整数m,表示最多能留在原地的花的株数。

输入输出样例

输入样例#1:

5
5 3 2 1 2

输出样例#1:

3

说明

【输入输出样例说明】
有多种方法可以正好保留 3 株花,例如,留下第 1、4、5 株,高度分别为 5、1、2,满足条件 B。

【数据范围】
对于 20% 的数据,$n \leq 10$;
对于 30% 的数据,$n \leq 25$;
对于 70% 的数据,$n \leq 1000, 0 \leq h_n \leq 1000$;
对于 100% 的数据,$n \leq 100,000, 0 \leq h_n \leq 1,000,000$,所有的$h_n$随机生成,所有随机数服从某区间内的均匀分布。

题解

对于70%这一档数据,有一个很暴力的DP思路。设dp[i][0]为第i株花结尾且该花为摆动序列中的峰值(极大值)时摆动序列的最大长度,dp[i][0]为第i株花结尾且该花为摆动序列中的谷值(极小值)时摆动序列的最大长度。
DP转移时,需要从i之前的花中找到dp[i][0]和dp[i][1]的最大值来计算。下面是形式化的转移方程

$$ \begin{matrix} dp[i][0] = \operatorname{max}_{1 \leq j < i, h_j < h_i} \{ dp[j][1] \} + 1 \\ dp[i][1] = \operatorname{max}_{1 \leq j < i, h_j > h_i} \{ dp[j][0] \} + 1 \end{matrix}$$

答案即是所有DP值中的最大值。
这是一个很好想的暴力做法,但是它的复杂度达到了$O(n^2)$,转移的复杂度为$O(n)$,无法通过100%的数据。

接下来我们考虑优化转移。我们用权值线段树维护“对应权值的DP值最大值”这样一个数据,每一次转移时,利用权值范围即可直接查出上述最大值。而每次转移统计完毕后,只需要把新的DP值插入线段树中指定的权值位置上即可。由于需要两种最大值(dp[i][0]和dp[i][1]),我们可以建立两棵线段树分别管理两种DP值。这种优化可以使转移复杂度降至$O(\log n)$,从而将总复杂度降至$O(n \log n)$,可以通过本题。

事实上,很多题解使用的简单$O(n)$DP存在利用随机数据较弱混过去的成分,读者在阅读这些题解时会存有疑惑,这是因为它们的做法实际上是错解,存在被忽视的特殊情况。

代码

// Code by KSkun, 2018/3
#include <cstdio>

#include <algorithm>
#include <vector>

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    char c = fgc(); 
    while (c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while (c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

// variables

const int MAXN = 100005;

int n, N, h[MAXN], f0, f1, ans = 0;
std::vector<int> tmp;

// seg tree

struct Node {
    int val, lch, rch;
} tree[MAXN << 3];

int rt0, rt1, tot = 0;

inline int build(int l, int r) {
    int p = ++tot;
    if(l == r) {
        return p;
    }
    int mid = (l + r) >> 1;
    tree[p].lch = build(l, mid);
    tree[p].rch = build(mid + 1, r);
    return p;
}

inline void modify(int p, int l, int r, int x, int v) {
    if(l == r) {
        tree[p].val = std::max(tree[p].val, v);
        return;
    }
    int mid = (l + r) >> 1;
    if(x <= mid) modify(tree[p].lch, l, mid, x, v);
    else modify(tree[p].rch, mid + 1, r, x, v);
    tree[p].val = std::max(tree[tree[p].lch].val, tree[tree[p].rch].val);
}

inline int query(int p, int l, int r, int ll, int rr) {
    if(ll > rr) return 0;
    if(l == ll && r == rr) {
        return tree[p].val;
    }
    int mid = (l + r) >> 1;
    if(rr <= mid) return query(tree[p].lch, l, mid, ll, rr);
    else if(ll > mid) return query(tree[p].rch, mid + 1, r, ll, rr);
    else return std::max(query(tree[p].lch, l, mid, ll, mid), query(tree[p].rch, mid + 1, r, mid + 1, rr));
}

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        h[i] = readint();
        tmp.push_back(h[i]);
    }
    std::sort(tmp.begin(), tmp.end());
    tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
    for(int i = 1; i <= n; i++) {
        h[i] = std::lower_bound(tmp.begin(), tmp.end(), h[i]) - tmp.begin() + 1;
    }
    N = tmp.size();
    rt0 = build(1, N);
    rt1 = build(1, N);
    for(int i = 1; i <= n; i++) {
        f0 = std::max(1, query(rt1, 1, N, 1, h[i] - 1) + 1);
        f1 = std::max(1, query(rt0, 1, N, h[i] + 1, N) + 1);
        ans = std::max(ans, std::max(f0, f1));
        modify(rt0, 1, N, h[i], f0);
        modify(rt1, 1, N, h[i], f1);
    } 
    printf("%d", ans);
    return 0;
}



发表回复

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

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据