题解

花匠小妙招
2024-11-13 04:26

花匠 https://ac.nowcoder.com/acm/contest/261/B

题目描述

花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。
具体而言，栋栋的花的高度可以看成一列整数 h1,h2,...,hn 。设当一部分花被移走后，剩下的花的高度依次为 g1,g2,...,gm ，则栋栋希望下面两个条件中至少有一个满足：
条件 A ：对于所有的i,g2i>g2i-1 ,且g2i>g2i+1
条件 B ：对于所有的i,g2i>g2i-1 ,且g2i<g2i+1
注意上面两个条件在 m=1 时同时满足，当 m > 1 时最多有一个能满足。
请问，栋栋最多能将多少株花留在原地。

输入描述:

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

输出描述:

一个整数 m ，表示最多能留在原地的花的株数。
示例1

输入

5
5 3 2 1 2

输出

备注

对于 20% 的数据， n ≤ 10 ；
对于 30% 的数据， n ≤ 25 ；
对于 70% 的数据， n ≤ 1000,0 ≤ hi≤ 1000 ；
对于 100% 的数据， 1 ≤ n ≤ 100,000,0 ≤ hi≤ 1,000,000 ，所有的 hi 随机生成，所有随机数服从某区间内的均匀分布。

解答

作为一道NOIP真题，这道题个人感觉比较水，稍稍用到了DP的思想；

我们仔细分析，发现两个条件可以总结为：求一个最长序列，使得该序列的任意三个相邻元素，中间的元素是三个中最大的，或者最小的；

对此，我们可以联想到最长不下降子序列，这道题我是由此想到正解的；

比如元素d[i]d[i]和d[j]d[j]，假设d[i]>d[j]d[i]>d[j]且j>ij>i，那么我们会让long[j]=max(long[j],long[i]+1)long_[j]=max(long_[j],long_[i]+1); 那么我们可以类比一下，最长不下降子序列是在当前节点前面找一个符合条件的，那么我们这道题也可以作为一道最长不下降子序列来做，只是当前节点寻找前驱的范围是前一个节点，而且我们还要用同样的方法求一个最长不上升子序列，最后取max，那么这道题就完了；

细节处理见代码：

(代码中的最高最低全部是以当前节点为中心时的相对值)

#include<iostream> #include<cstdio> #define II int #define R register #define I 123456 using namespace std; II a[I],d_1[I],d_2[I]; II n; int main() { // freopen("FlowerNOIP2013.in","r",stdin); // freopen("FlowerNOIP2013.out","w",stdout); scanf("%d",&n); R II x; for(R II i=1;i<=n;i++) scanf("%d",&x), a[i]=x; d_1[1]=d_2[1]=1; //d_1[]代表的是当前元素是以当前元素为中心的三个相邻的元素中最大的； //同理，d_2[]代表的是当前元素是以当前元素为中心的三个相邻的元素中最小的； //但是当前元素不一定选，可能是继承上一个元素的信息； for(R II i=2;i<=n;i++) { if(a[i]>a[i-1]) d_1[i]=max(d_1[i-1],d_2[i-1]+1), d_2[i]=d_2[i-1]; //如果当前元素大于这个前一个元素； //那么当前元素若果选，则是前一个元素作为最低点时的长度+1； //如果不选，就继承前一个元素作为最高点，等价于当前元素作为最高点； //当前元素作为最低点就只能继承前一个点作为最低点； else{ if(a[i]<a[i-1]) d_1[i]=d_1[i-1], d_2[i]=max(d_1[i-1]+1,d_2[i-1]); //如果当前元素小于前一个元素，则道理同上，只是反过来； else d_1[i]=d_1[i-1], d_2[i]=d_2[i-1]; //如果当前元素等于前一个元素，那么这个元素直接继承前一个元素的所有信息； //因为这两个点是完全等价的； } } R II ans=max(d_1[n],d_2[n]); //我们在最后时取两种状态的最大值作为答案； cout<<ans<<endl; return 0; }

来源：wuzhoupei