花匠

原题链接：https://www.luogu.org/problem/show?pid=1970

题面可能有同学看着比较懵逼，其实不难理解。

它要求的是找一个抖动序列。啥叫抖动序列？

如果a[i-1]>a[i]那么a[i]<a[i+1]，如果a[i-1]<a[i]那么a[i]>a[i+1]

类似于一个折线的样子。

也有的题解说是找拐点，这话也对。这道题看起来很像dp，不过贪心就可以过。

可以看出，最后的序列肯定是一大一小一大或者一小一大一小，并且题目中问的是最后最多剩多少花，那么贪心思想就明确了。要求剩最多的花，也就是让拿走的花尽量少，那么我们想从这个序列中取出一个最长的抖动序列，如果要在一堆上升的花中拿一个，拿哪一个？自然是拿最高的一个，这样接下来去考虑拿下降的花的时候，就不必担心拿走更多的。在下降花中同理，拿一个最低的，这样就不必考虑拿走更多的上升的花。

连数组都不用，读入的时候直接处理就好。我们从第二株花进行考虑，因为第一株无论如何都是要取的，循环时维护上一株花的高度，如果相等则直接去掉当前株。开一个变量d维护高度差以判断上升还是下降，每找到一株合法的花就让ans++，直到循环结束，最后的答案就是ans+1（因为循环的时候没有算第一株）。

代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 inline int read(){
 6     int num = 0;
 7     char c;
 8     bool flag = false;
 9     while ((c = getchar()) == ' ' || c == '
' || c == '
');
10         if (c == '-') flag = true;
11     else
12         num = c - '0';
13     while (isdigit(c = getchar()))
14     num = num * 10 + c - '0';
15     return (flag ? -1 : 1) * num;
16 }
17 int n,st,t,d,ans;
18 int main(){
19     n = read();
20     st = read();
21     for (int i=2;i<=n;i++){
22         t = read();
23         if ((t-st != 0) && ((d>0 && t<st) || (d<0 && t>st) ||d==0)){
24             ans++;
25             d = t - st;
26         }
27         st = t;
28     }
29     cout << ans+1 << endl;
30     return 0;
31 }