题目地址

https://www.luogu.org/problemnew/show/P1970

题目描述

花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定

把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希

望剩下的花排列得比较别致。

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

条件 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时最多有一个能满足。

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

输入输出格式

输入格式：

输入文件为 flower .in。

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

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

输出格式：

输出文件为 flower .out。

输出一行，包含一个整数m，表示最多能留在原地的花的株数。

输入输出样例

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

思路

看到这个题，很容易联想到最长上升子序列，但是要想找出其中的联系，又似乎没有那么容易，其实我们模拟一下就可以知道大概地思路了

5 3 4 2 4 6 2 1 4

例如上面这个样例，按照题意，必须按照一上一下排列，那么就有先上和现下两种情况，我们不妨分开讨论（其实思路是一样的）。

    我们以先找向下的数为例， 我们先将5放入一个数组f，表示5要保留，然后我们要找一个更小的数，恰好3比5小，所以将3也放入数组，继续

我们就要找一个更大的数，恰好4比3大，放入，然后更小得数，2放入，然后更大，4放入（好巧..），然后我们要找更小的数，但是

6比4大，然后我们考虑，以一个更大的数为标准找跟小的数，可以找到的更多数，所以我们用6更新掉4，也就是将4移走（这就是与最

长上升子序列相似的地方）。当然，如果找到的数与当前的数一样，那么久按照第二种方法处理。

　　　然后我们按照同样的方法找一遍现找向上的数，取两个长度中的大的一个。最后就是答案了（似乎比最长上升子序列更简单......）、

　　具体代码实现的话，我的思路是可以找一个变量记录方向，然后每次找到新点之后，将方向改变（所谓方向，其实就是下一个点要更大还是更小），用一个数组f

来存放进去的数（既留下的数），并用一个变量len来记录它的长度，最后输出长度就好了。

代码

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 int n,a[100010],f[100010];
 5 bool fx=0;//0时找更小的，1时找更大的 
 6 int main()
 7 {
 8      scanf("%d",&n);
 9      for(int i=1;i<=n;++i)
10      {
11          scanf("%d",&a[i]);//用a来存花的高度
12      }
13      int len1=0;//len用来记录留下花的个数
14      f[++len1]=a[1];//先将第一个放入
15      fx=0;//先寻找更小的
16      for(int i=2;i<=n;++i)
17      {
18         if(fx==0)
19          {
20             if(a[i]<f[len1])//符合要求就放入
21              { 
22             f[++len1]=a[i];
23             fx=1;//改变方向
24             }        
25             else//不符合要求就更新当前点（不用改变方向）
26             f[len1]=a[i];
27          }
28         if(fx==1)//同样方法判断向上找的情况
29          {
30             if(a[i]>f[len1])
31             {
32              f[++len1]=a[i];
33              fx=0;
34              }    
35              else
36              f[len1]=a[i];
37          }
38      }
39      memset(f,0,sizeof(f));
40      int len2=0;//与上方雷同，只不过实现找更大的
41      f[++len2]=a[1];
42      fx=1;
43      for(int i=2;i<=n;++i)
44      {
45          if(fx==0)
46          {
47              if(f[len2]>a[i])
48             {
49                  f[++len2]=a[i];
50                  fx=1;
51              }
52              else
53              f[len2]=a[i];
54          }
55          if(fx==1)
56          {
57              if(f[len2]<a[i])
58              {
59                  f[++len2]=a[i];
60                  fx=0;
61              }
62              else
63             f[len2]=a[i];
64         }
65     }
66     printf("%d",max(len1,len2));//输出两种情况中更大的一种情况
67      return 0;
68  }