题解：P1970 [NOIP2013 提高组] 花匠

· · 题解

思路：

提供一个根本不需要数组的方法。

主要是看题解区都是用数组，所以这个不用数组的方法告诉大家。

这道题实际上只需要贪心找折线就可以了。

做法其实不是太难想。这道题其实就是找到一个最长的波浪序列（每一盆花都是波峰或波谷）。

首先，对于第一盆花，不论如何都要选，因为如果不选，第二盆花就相当于第一盆，而花的总数却减少了，所以一定不会更优。

对于第二盆花，如果和第一盆等高，就没有用，可以直接不选（这时候还是找第二盆）；如果比第一盆高，那么它就一定要作为波峰（如果作为波谷则等同于第一盆没选）；同理如果比第一盆低就一定是波谷。

对于后面的花，如果找波峰，如果当前花比上一盆高，那么波峰就找到了，接下来找波谷；如果不如上一盆高，那么用这盆更低的花继续找波峰结果一定不会更差。找波谷同理。

在操作过程中记录留下多少花即可。

code：

代码如果不懂可以私信我（记得关注我）。

#include <bits/stdc++.h>
using namespace std;

int n, m, t = 0, ans = 1, cnt = -1;

int main() {
    scanf("%d %d", &n, &m);
    t = m;
    for (int i = 2; i <= n; i++) {
        scanf("%d", &m);
        if (m > t && cnt != 1) {
            cnt = 1;
            ans++;
        } else if (m < t && cnt) {
            cnt = 0;
            ans++;
        }
        t = m;
    }
    printf("%d\n", ans);
    return 0;
}