直接粘题解+代码。

这个题解比其他的DP不知道高到哪里去了，吼哇！

/// //

【背景】 作为往年的noip题，我曾经当作dp题写过，时间比较吃紧。

但是我最近做的一套模拟题里有这道题的强化（数据强化为10000000，时间变为2秒），所以不得不思考贪心做法（要用读入优化）。

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

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

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

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

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

结合代码思考一下。

【代码】（看不懂可以私信我）

1 #include
     
       2 #include
      
        3 using namespace std; 4 bool flag1,flag2;//flag1:是否找到第二盆花;flag2:当前找波峰还是波谷，1:找波峰; 0:找波谷  5 int n,lst,h,ans;//h:当前花高度;lst:上一盆花高度;ans:答案  6 inline int red() 7 { 8     int X=0,w=1; 9     char ch=0;10     while(ch<'0'||ch>'9')11     {12         if(ch=='-')13         {14             w=-1;15         }16         ch=getchar();17     }18     while(ch<='9'&&ch>='0')19     {20         X=(X<<3)+(X<<1)+ch-'0';21         ch=getchar();22     }23     return X*w;24 }25 int main()26 {27 //    freopen("flower.in","r",stdin);freopen("flower.out","w",stdout);28     n=red();29     int i=0;30     for(i=1;i<=n;i++)31     {32         h=red();33         if(i==1)34         {35             lst=h;36             ans++;37         }38         else if(!flag1)//如果没找到第二盆花 39         {40             if(h>lst)41             {42                 ans++;43                 flag1=1;//表示已经找到第二盆花 44                 lst=h;45             }46             else if(h
       
        lst)68                 {69                     ans++;70                     flag2=0;//已找到波峰，接下来找波古 71                 }72                 lst=h;73             }74         }75     }76     printf("%d\n",ans);77     return 0;78 }
       
      
     

 

///

 

我的代码：

1 #include 
     
       2 using namespace std; 3  4 int h[100004],last; 5 int n,ans=2; 6 bool flag;///false找大,true找小 7  8 int main() 9 {10     scanf ("%d",&n);11     scanf ("%d",&h[1]);12     int i=2;13     while(!last)14     {15         scanf ("%d",&h[i]);16         if(h[i]==h[1])17         {18             i++;19             continue;20         }21         if(h[i]>h[1]) flag=1;22         last=h[i];23         i++;24     }25     for(;i<=n;i++)26     {27         scanf ("%d",&h[i]);28 29 30 31         if(h[i]==last) continue;32         else if(h[i]>last)33         {34             if(!flag)35             {36                 ans++;37                 flag=1;38             }39             last=h[i];40         }41         else42         {43             if(flag)44             {45                 ans++;46                 flag=0;47             }48             last=h[i];49         }50 51 52 /*53         if(flag)54         {55             if(h[i]
      
       last)65             {66                 flag=1;67                 ans++;68             }69             last=h[i];70         }71 72         */73 74     }75     printf("%d",ans);76     return 0;77 }