爱国者的周期

爱国者的周期

测试数据来自 system/1686

背景

Talent先生在玩红色警戒(2100年最新版)...

这种版本的红色警戒中“爱国者飞弹”是一种强大的防空武器,无论敌方的什么空军以什么高度入侵,只要“爱国者”对它进行攻击,都可以做到弹无虚发,中弹必亡....(ms有点厉害的过了头....)

描述

然而...它有一个缺点....“爱国者”并不总是可以连续的对全部的敌方空军进攻击..
对于每个“爱国者”都有一个“连续攻击高度的半周期”:T。(10>=T>=1)
当敌方的一排空军袭来时...
从攻击第一个目标开始,设“爱国者”攻击的第“i”个目标高度为:H[i];

则必须满足:
(k是自然数)则在每个全周期的区间[2KT+1,2(K+1)T+1]里,
前半个周期[2KT+1,(2K+1)T+1]里,H[i]是严格单调递减的...
后半个周期[(2K+1)T+1,2(K+1)T+1]里,H[i]是严格单调递增的...
注:[a,b]表示:a<=i<=b

换种方法描述..
有以下的特点:H[1] > H[2] >... H[T] >H[T+1]
H[T+1] < H[T+2] <... H[2T] <H[2T\+1]
H[2T\+1] > H[2T+2] >... H[3T] >H[3T+1]
H[3T+1] < H[3T+2] <... H[4T] <H[4T\+1]
\.
\.
\.
H[2KT\+1] > H[2KT+2] >...H[(2K+1)T]>H[(2K+1)T+1]
H[(2K+1)T+1]<H[(2K+1)T+2]<...H[2(K+1)T]<H[2(K+1)T+1]
现在,敌人的空军来了(排列成一列,并且一个一个进入“爱国者”的射程范围之内)
你可以控制你的“爱国者”攻击或不攻击某个敌军的空军单位...
并且一个单位进入你的射程后,你必须立即决定攻击或不攻击,否则就没有机会再攻击它....

现在,请你编一个程序,依次给你将要进入你的射程的范围的敌方空军的高度
,输出,如果你用最优的操作方式,做多能攻击几个敌军的空军单位...

格式

输入格式

第一行:两个整数N,turn(分别代表敌军的数量和半周期)
第二行:N个整数(依次代表敌军各个单位的高);

输出格式

只有一行:一个整数,代表最多能击落几个敌军的单位。

样例1

样例输入1

10 1
1 3 2 4 5 6 9 7 8 10

样例输出1

5

限制

对于100%的数据 N<=2000,turn<=10

共有5个测试数据,每个测试数据包含1个测试点

来源

本题目来自:北京市,中关村中学,高三9班,孙一(Talent教主),联系方式:865383864(QQ)

信息

ID
1755
难度
(无)
分类
动态规划 | 动态规划 | LIS 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者