华师一附中OI组

标题: P1970 花匠 [打印本页]

---

作者: YTC    时间: 2018-6-5 17:10
标题: P1970 花匠
https://www.luogu.org/problemnew/show/P1970

题目描述
花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。

具体而言，栋栋的花的高度可以看成一列整数 h_1,h_2,...,h_n。设当一部分花被移走后，剩下的花的高度依次为 g_1,g_2,...,g_m ，则栋栋希望下面两个条件中至少有一个满足：

条件 A：对于所有 g_2i>g_2i-1,g_2i>g_2i+1

​         

条件 B ：对于所有 g_2i<g_2i-1,g_2i<g_2i+1

​         

注意上面两个条件在 m=1时同时满足，当 m > 1时最多有一个能满足。

请问，栋栋最多能将多少株花留在原地。

输入输出格式
输入格式：
第一行包含一个整数 n ，表示开始时花的株数。

第二行包含 n 个整数，依次为 h_1,h_2,...,h_n ,表示每株花的高度。

输出格式：
一个整数 m ，表示最多能留在原地的花的株数。

输入输出样例
输入样例#1：
5
5 3 2 1 2
输出样例#1：
3

---

作者: 胡雨菲菲    时间: 2018-6-5 18:02

1. #include <cstdio>
   
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.         else
    
42.         {
    
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)
    
56.             {
    
57.                 flag=0;
    
58.                 ans++;
    
59.             }
    
60.             last=h[i];
    
61.         }
    
62.         else
    
63.         {
    
64.             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. }
    

复制代码

---

作者: YTC    时间: 2018-6-13 13:03
法一：DP
用两个数组分别记录到i下降和到i上升

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int N=100010
   
4. int a[N],f[N][2];
   
5. int n,tmp=0;
   
6. int main(){
   
7.     scanf("%d",&n);
   
8.     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
   
9.     f[1][0]=f[1][1]=1;
   
10.     for(int i=2;i<=n;i++){
    
11.         if(a[i]>a[i-1])f[i][0]=f[i-1][1]+1;
    
12.         else f[i][0]=f[i-1][0];
    
13.         if(a[i]<a[i-1])f[i][1]=f[i-1][0]+1;
    
14.         else f[i][1]=f[i-1][1];
    
15.     }
    
16.     cout<<max(f[n][0],f[n][1]);
    
17.     return 0;
    
18. }

复制代码

---

作者: YTC    时间: 2018-6-13 13:09
法二：贪心

复制一波洛谷的题解

/*这道题其实就是找到一个最长的波浪序列（每一盆花都是波峰或波谷）。

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

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

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

在操作过程中记录留下多少花即可。
*/
楼上dalao就是这样写的

下面是本蒟蒻的代码

1. #include<iostream>
   
2. using namespace std;
   
3. int a[100005];
   
4. int n,p;
   
5. int ans1,ans2;
   
6. int now;
   
7. int main()
   
8. {
   
9.     cin>>n;
   
10.     for(int i=1;i<=n;i++) cin>>a[i];
    
11.     p=0;
    
12.     now=a[1];
    
13.     ans1=1;
    
14.     for(int i=2;i<=n;i++)
    
15.     {
    
16.         if(p==0)
    
17.             if(now>a[i])
    
18.         {
    
19.             ans1++;
    
20.             now=a[i];
    
21.             p=1;
    
22.         }
    
23.         else now=a[i];
    
24. 
    
25.         if(p==1)
    
26.             if(now<a[i])
    
27.         {
    
28.             ans1++;
    
29.             now=a[i];
    
30.             p=0;
    
31.         }
    
32.         else now=a[i];
    
33.     }
    
34.     p=1;
    
35.     now=a[1];
    
36.     ans2=1;
    
37.     for(int i=2;i<=n;i++)
    
38.     {
    
39.         if(p==0)
    
40.             if(now>a[i])
    
41.         {
    
42.             ans2++;
    
43.             now=a[i];
    
44.             p=1;
    
45.         }
    
46.         else now=a[i];
    
47.         if(p==1)
    
48.             if(now<a[i])
    
49.         {
    
50.             ans2++;
    
51.             now=a[i];
    
52.             p=0;
    
53.         }
    
54.         else now=a[i];
    
55.     }
    
56.    cout<<max(ans1,ans2);
    
57.     return 0;
    
58. }

复制代码

---

作者: YTC    时间: 2018-6-13 13:14
对贪心思路进行分析，可知只需找波峰和波谷即可

下面是洛谷题解的代码

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int n,h[1000005],ans=1;bool con;
   
4. int main()
   
5. {
   
6.     cin>>n;for(int i=1;i<=n;i++) cin>>h[i];
   
7.     if(h[2]>=h[1]) con=1;
   
8.     for(int i=1;i<=n;i++)
   
9.     {
   
10.         if(con==0&&i==n) {ans++;break;}
    
11.         if(con==1) if(h[i+1]<h[i]){ans++;con=0;continue;}
    
12.         if(con==0) if(h[i+1]>h[i]) {ans++;con=1;continue;}
    
13.     }
    
14.     cout<<ans;
    
15. }

复制代码

注意特判第二朵来贪心，最后一朵一定保留

---

作者: 吴语林    时间: 2018-7-30 00:06

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. int n,j,all=0,l,x,e=1;
    
14. int main()
    
15. {
    
16.         scanf("%d%d",&n,&l);n--;
    
17.         while(e)
    
18.         {
    
19.                 scanf("%d",&x);
    
20.                 n--;
    
21.                 if(l<x)
    
22.                         j=1,all=2,l=x,e=0;
    
23.                 else if(l>x)
    
24.                         j=0,all=2,l=x,e=0;
    
25.         }
    
26.         while(n--)
    
27.         {
    
28.                 scanf("%d",&x);
    
29.                 if(j==1)
    
30.                 {
    
31.                         if(l>x)
    
32.                                 j=0,all++;
    
33.                         l=x;
    
34.                 }
    
35.                 else
    
36.                 {
    
37.                         if(l<x)
    
38.                                 j=1,all++;
    
39.                         l=x;
    
40.                 }
    
41.         }
    
42.         printf("%d",all);
    
43.         return 0;
    
44. }

复制代码

---

作者: universehyf    时间: 2018-9-25 20:34

1. #include<iostream>
   
2. using namespace std;
   
3. #define FOR(iii,nn,mm) for(int iii=nn;iii<=mm;iii++)
   
4. long long h[100010];
   
5. long long n,c,ans=2,t;
   
6. int main()
   
7. {
   
8.     cin>>n>>h[0];FOR(i,1,n-1) {cin>>t;if(t!=h[c]) h[++c]=t;}
   
9.     FOR(i,1,c-1) if((h[i]-h[i-1])*(h[i]-h[i+1])>0) ans++;
   
10.     c==0?cout<<1:cout<<ans;
    
11.     return 0;
    
12. }

复制代码

---

作者: admin    时间: 2018-9-26 16:57
楼上HYF的程序好牛呀  短小精悍

---

作者: universehyf    时间: 2018-9-26 19:49


这是我看了蒋轩林的程序写的代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2