[NOIP 2013 提高组] 花匠

题意

给出一排花的高度，可以删除一些花，但剩下的花相对顺序不能变。

要求保留下来的高度序列满足“高低交替”或“低高交替”，问最多能保留多少朵花。

思路

最直接的教学做法是最长摆动子序列 DP。

先看一个可以直接验证想法的朴素解：

cpp

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#include <bits/stdc++.h>
using namespace std;

// brute.cpp：O(n^2) DP，枚举最后一朵保留的花。

const int MAXN = 1005;

int n;
int h[MAXN];
int up[MAXN];
int down[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }

    int ans = 1;

    for (int i = 1; i <= n; i++) {
        up[i] = 1;   // 以 i 结尾，最后一段是上升
        down[i] = 1; // 以 i 结尾，最后一段是下降

        for (int j = 1; j < i; j++) {
            if (h[i] > h[j]) {
                up[i] = max(up[i], down[j] + 1);
            } else if (h[i] < h[j]) {
                down[i] = max(down[i], up[j] + 1);
            }
        }

        ans = max(ans, max(up[i], down[i]));
    }

    cout << ans << '\n';
    return 0;
}

下面是另一种「01 序列」风格的暴力写法。它按花的下标依次决定“保留 / 删除”，递归生成完整选择后，叶子节点统一检查保留下来的序列是否摆动，并统计最长长度：

另一种暴力写法：01 序列

cpp

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// brute_01_style.cpp：01 序列风格暴力，按花的下标依次决定保留或删除。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 30;

int n;
int h[MAXN];
int keep_flower[MAXN]; // keep_flower[i] = 0/1，表示第 i 朵花删除/保留
int answer;

bool check() {
    int last_height = 0;
    int last_sign = 0;
    int count_chosen = 0;
    for (int i = 1; i <= n; i++) {
        if (keep_flower[i] == 0) continue;
        if (count_chosen > 0) {
            if (h[i] == last_height) return false;
            int cur_sign = (h[i] > last_height ? 1 : -1);
            if (last_sign != 0 && cur_sign == last_sign) return false;
            last_sign = cur_sign;
        }
        last_height = h[i];
        count_chosen++;
    }
    return true;
}

int calc_answer() {
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (keep_flower[i] == 1) cnt++;
    }
    return cnt;
}

void dfs_choose(int dep) {
    if (dep == n + 1) {
        if (check()) {
            int value = calc_answer();
            if (answer < value) answer = value;
        }
        return;
    }

    for (int i = 0; i <= 1; i++) {
        keep_flower[dep] = i;
        dfs_choose(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }

    answer = 0;
    dfs_choose(1);

    cout << answer << '\n';
    return 0;
}

在 brute.cpp 里：

up[i] 表示以第 i 朵花结尾，最后一段是上升的最长长度
down[i] 表示以第 i 朵花结尾，最后一段是下降的最长长度

枚举前一个位置 j，就能做出 $O(n^2)$ 转移。

这个版本容易理解，但 $n = 10^5$ 时过不了。

接下来观察贪心性质。

如果一段趋势一直上升，例如：

1, 3, 5, 6

那么中间的 3, 5 其实都不重要。对后续来说，保留最后的 6 总不会更差，因为它更容易和后面形成一次下降转折。

下降段也完全一样。

所以真正重要的只有“转折点”。

把相邻差值记成：

diff[i] = h[i] - h[i-1]

我们只需要统计：

第一次出现非零差值
差值符号从正变负，或者从负变正

每发生一次这样的事件，就说明最长摆动序列长度可以增加 1。

样例表

样例 5 3 2 1 2 的相邻差值如下：

位置	高度	相邻差值符号	当前答案
1	`5`	无	`1`
2	`3`	`-`	`2`
3	`2`	`-`	`2`
4	`1`	`-`	`2`
5	`2`	`+`	`3`

可以看到，前面一直下降时，答案不会重复增加；只有最后一次从下降变成上升时，才形成新的转折点，所以最终答案是 3。

DP 公式

可以把最长波动序列压成两个状态。设 $up_i$ 表示以第 $i$ 盆花结尾且最后一段是上升的最长长度， $down_i$ 表示最后一段是下降的最长长度。若 $h_i>h_{i-1}$ ：

up_i=down_{i-1}+1,\quad down_i=down_{i-1}

若 $h_i<h_{i-1}$ ：

down_i=up_{i-1}+1,\quad up_i=up_{i-1}

若 $h_i=h_{i-1}$ ，两个状态保持不变。答案为：

\max(up_n,\ down_n)

公式解释：花匠要求高度趋势不断改变，所以只需知道当前最后一段是上升还是下降。遇到上升差值时，只能接在下降状态后形成新转折；遇到下降差值时则反过来。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
int h[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }

    if (n == 1) {
        cout << 1 << '\n';
        return 0;
    }

    int ans = 1;
    int last_sign = 0; // 0: 还没有方向, 1: 上升, -1: 下降

    for (int i = 2; i <= n; i++) {
        int diff = h[i] - h[i - 1];
        if (diff == 0) {
            continue;
        }

        int cur_sign = (diff > 0 ? 1 : -1);

        // 第一次出现有效方向，或者方向发生变化时，都可以把当前花留下。
        if (last_sign == 0 || cur_sign != last_sign) {
            ans++;
            last_sign = cur_sign;
        }
    }

    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n)$
空间复杂度： $O(1)$

总结

这题的本质是最长摆动子序列。

关键不是保留所有中间点，而是抓住每一段单调趋势的末端。在线性扫描中统计趋势变化次数，就能得到最优答案。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。