| 题目名称 | 1441. [NOIP 2013]花匠 |
|---|---|
| 输入输出 | FlowerNOIP2013.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 超级傲娇的AC酱
于2013-11-18加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：387， 提交：990， 通过率：39.09% | ||||
 521 |
100 | 0.000 s | 0.00 MiB | C++ |
 dateri |
100 | 0.000 s | 0.00 MiB | C++ |
 柯哀王道 |
100 | 0.000 s | 0.00 MiB | C++ |
|
柯哀王道 |
100 | 0.000 s | 0.00 MiB | C++ |
 Furyton |
100 | 0.000 s | 0.00 MiB | C++ |
 ~玖湫~ |
100 | 0.000 s | 0.00 MiB | C++ |
|
~玖湫~ |
100 | 0.000 s | 0.00 MiB | C++ |
 LGLJ |
100 | 0.000 s | 0.00 MiB | C++ |
 ignitedark |
100 | 0.000 s | 0.00 MiB | C++ |
 Youngsc |
100 | 0.001 s | 0.07 MiB | C++ |
| 关于 花匠 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
骚骚的贪心～～～
| ||||
|
快到联赛状态超差，各种低级错误。(>﹏<)
| ||||
|
woc
$O(n^{2})$暴力有80 老夫线段树优化一下看能不能过 | ||||
|
贪心，结果输入搞错了qwq，焦虑.jpg
| ||||
|
n方DP调了半天调不出来，被旁边神犇提醒要输出最大保留个数，还交了一发玄学+1版2333
 荡漾
2017-09-20 20:33
36楼
| ||||
|
这算什么做法
| ||||
|
玄学超时？？！！
| ||||
|
回复 @Drench :
nlgn线段树竟然70分  +1s
2017-09-09 16:11
33楼
| ||||
|
向贪心过的大佬低头
| ||||
|
二维DP强行加线段树乱搞O(nlogn)AC了.....。。。。
| ||||
WHZ0325
Hzoi_Mafia
芒硝
BFZD
CSU_Turkey
hee【题目描述】
花匠栋栋种了一排花，每株花都有自己的高度。花儿越长越大，也越来越挤。栋栋决定把这排中的一部分花移走，将剩下的留在原地，使得剩下的花能有空间长大，同时，栋栋希望剩下的花排列得比较别致。
具体而言，栋栋的花的高度可以看成一列整数$h_1,h_2,\cdots,h_n$。设当一部分花被移走后，剩下的花的高度依次为$g_1,g_2,\cdots,g_n$，则栋栋希望下面两个条件中至少有一个满足：
条件 A：对于所有的$i$，$g_{2i}>g_{2i-1}$，且$g_{2i}>g_{2i+1}$；
条件 B：对于所有的$i$，$g_{2i}<g_{2i-1}$，且$g_{2i}<g_{2i-1}$。
注意上面两个条件在$n=1$时同时满足，当$m>1$时最多有一个能满足。
请问，栋栋最多能将多少株花留在原地。
【输入格式】
输入的第一行包含一个整数n，表示开始时花的株数。
第二行包含n个整数，依次为$h_1,h_2,\cdots,h_n$，表示每株花的高度。
【输出格式】
输出一行，包含一个整数m，表示最多能留在原地的花的株数。
【样例输入】
5 5 3 2 1 2
【样例输出】
3
【样例说明】
有多种方法可以正好保留 3 株花，例如，留下第 1、4、5 株，高度分别为 5、1、2，满足条件 B。
【数据规模与约定】
对于20%的数据，$n\leq 10$；
对于30%的数据，$n\leq 25$；
对于70%的数据，$n\leq 1000,0\leq h_i\leq 1000$；
对于100%的数据，$1\leq n\leq 100,000,0\leq h_i\leq 1,000,000$，所有的$h_i$随机生成，所有随机数服从某区间内的均匀分布。
【来源】
NOIP2013 Day2 Task2