首先这道题可以用DP模仿最长上升子序列得到80分，然后我们来考虑一下正解应该怎么写。题意可以简化为选择尽可能多的花组成一个波浪型，然后我们我考虑，在每一个波峰上，在不影响后续的情况下，选取尽可能大的情况最顶最优。在波谷上，在不影响后续的情况下，选取尽可能小的情况也一定最优秀。因为尽可能大/小，我们后续的选择余地就更大。所以我们可以进行贪心。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 int n,ans1,ans2; 5 int vec[200000]; 6 bool top; 7 int main() 8 { 9 scanf("%d",&n); 10 for (int i = 1;i <= n;i++) 11 scanf("%d",&vec[i]); 12 ans1 = 1; 13 for (int i = 2;i <= n;i++) 14 { 15 if (!top) 16 { 17 if (vec[i] > vec[i - 1]) 18 { 19 ans1++; 20 top = true; 21 } 22 }else 23 { 24 if (vec[i] < vec[i - 1]) 25 { 26 ans1++; 27 top = false; 28 } 29 } 30 } 31 top = true; 32 ans2 = 1; 33 for (int i = 2;i <= n;i++) 34 { 35 if (!top) 36 { 37 if (vec[i] > vec[i - 1]) 38 { 39 ans2++; 40 top = true; 41 } 42 }else 43 { 44 if (vec[i] < vec[i - 1]) 45 { 46 ans2++; 47 top = false; 48 } 49 } 50 } 51 52 printf("%d\n",max(ans1,ans2)); 53 return 0; 54 }
原文：https://www.cnblogs.com/iat14/p/11520199.html