OpenJudge

16:Ski Lift----动规,好象要优化一点

总时间限制:
10000ms
单个测试点时间限制:
1000ms
内存限制:
1024kB
描述
建造滑雪场的升降轨道。起点和终点的高度已知,x坐标分割成若干份,间隔为1,每一点都给出支架的高度。要选择尽可能少的支架顶端建立固定点,两个固定点之间用一条直钢轨连接,当然要求中间支架的高度都不能超过钢轨在那里的高度。而且两个相邻固定点之间的距离不能超过给定的K。
输入
第一行是N和K,2<=N<=5000,1<=K<=N-1。
接下来N行,按顺序是支架的高度h,0<=h<=1000000000。
输出
一个整数,表示最少要选择几个固定点。第一个(起点)和最后一个(终点)一定是固定点。
样例输入
13 4
0
1
0
2
4
6
8
6
8
8
9
11
12
样例输出
5

说明:可以选择第1、5、7、9、13个支架作为固定点。而且至少需要5个固定点。
提示
测试数据下载:http://u.115.com/file/bha7lz22#
skilift.rar
全局题号
3617
添加于
2011-07-18
提交次数
4
尝试人数
3
通过人数
0