博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
CODEVS 3289 花匠
阅读量:7117 次
发布时间:2019-06-28

本文共 1357 字,大约阅读时间需要 4 分钟。

【题目描述 
Description】

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

具体而言,栋栋的花的高度可以看成一列整数h_1, h_2, … , h_n。设当一部分花被移走后,剩下的花的高度依次为g_1, g_2, … , g_m,则栋栋希望下面两个条件中至少有一个满足:
条件 A:对于所有的1<i<m/2,g_2i > g_2i-1,且g_2i > g_2i+1; 
条件 B:对于所有的1<i<m/2,g_2i < g_2i-1,且g_2i < g_2i+1。
注意上面两个条件在m = 1时同时满足,当m > 1时最多有一个能满足。
请问,栋栋最多能将多少株花留在原地。

输入描述 
Input Description

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

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

输出描述 
Output Description

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

样例输入 
Sample Input

5 3 2 1 2

样例输出 
Sample Output

3

【数据范围及提示 
Data Size & Hint】

对于 20%的数据,n ≤ 10; 

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

【解题思路】

给的标签是神马序列性DP,写了半天方程愣是没敲出来,再然后我去看了两眼题解才知道这是一个贪心,去重之后,把连续上升子序列和连续下降子序列中间的部分都去掉,然后减掉,就能过了。

1 program flower;{
T4} 2 var a,a1:array[1..100000] of longint; 3 n,i,ans,m:longint; 4 begin 5 read(n); 6 read(a1[1]); 7 m:=1; 8 a[m]:=a1[1]; 9 for i:=2 to n do//去重10 begin11 read(a1[i]);12 if a1[i]<>a[m] then13 begin14 inc(m);15 a[m]:=a1[i];16 end;17 end;18 ans:=m;19 for i:=2 to m-1 do20 begin21 if (a[i-1]>a[i]) and (a[i]>a[i+1]) then dec(ans);22 if (a[i-1]

 

转载于:https://www.cnblogs.com/wuminyan/p/4746206.html

你可能感兴趣的文章
ECLIPSE MYECLIPSE 在线安装SVN
查看>>
开源《热血传奇》服务端引擎(C#编写),可以顺利进行游戏(更新编译和部署教程)...
查看>>
缓存线程池的作用
查看>>
utf-8变长
查看>>
缩小 UIImage 的代码
查看>>
Hi3716CV200
查看>>
js将相除结果百分比 ,四舍五入函数 toFixed()
查看>>
IOS 多线程 NSThread
查看>>
Python入门
查看>>
iis部署网站
查看>>
Turn the corner
查看>>
Flipper
查看>>
Jmeter元件的作用域与执行顺序
查看>>
SQL Server 分组操作解析
查看>>
Spring集成RabbitMQ-使用RabbitMQ更方便
查看>>
找硬币
查看>>
bzoj3190[JLOI2013]赛车
查看>>
bzoj4716假摔
查看>>
object-c中数组的排序
查看>>
Es6学习笔记
查看>>