首页 > 试题广场 >

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种

[问答题]

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000 的正整数），计算这套系统最多能拦截多少导弹?该导弹数量不超过100个。

推荐

1185925亓乂

参考答案

解题思路：
动态规划

评分标准：
标准的动态规划，就是求最长不上升子序列，能将问题建立模型，归为求最长不上升子序列问题，可酌情给分10%－20%；
通过完整动态规划策略（状态转移方程为：dp1[i] = max(dp1[j]) + 1, j从1到i-1且a[j] > a[i]）给出解题过程，
测试数据包含：正常测试数据（80%－90%）；空测试数据集合等边界情况（10%－20%）；

发表于 2018-08-13 20:39:25 回复(0)