某国为了防御敌国的导弹袭击,开发出一种导弹拦截系统,但是这种拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度, 但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭,由于该系统还在试用阶段。所以一套系统有可能不能拦截所有的导弹。 输入导弹依次飞来的高度(雷达给出的高度不大于30000的正整数)。计算要拦截所有导弹最小需要配备多少套这种导弹拦截系统。 【输入格式】 n颗依次飞来的高度(1≤n≤1000). 【输出格式】 要拦截所有导弹最小配备的系统数k。 【输入样例】missile.in 389 207 155 300 299 170 158 65 【输出样例】missile.out 2 【输入输出样例】 输入:导弹高度: 7 9 6 8 5 输出:导弹拦截系统K=2 输入:导弹高度: 4 3 2 输出:导弹拦截系统K=1
时间: 2024-04-09 14:27:29 浏览: 146
安卓毕业设计app项目源码6-privacygeek:隐私极客PrivacyGeek
这是一个典型的动态规划问题。我们可以用一个数组dp来记录每个位置上的最长递减子序列长度。初始时,dp数组的所有元素都为1,表示每个导弹都可以单独配备一个拦截系统。
然后我们从第2个导弹开始遍历,对于每个导弹的高度,我们从第一个导弹开始向前遍历,如果前面的导弹高度严格大于当前导弹高度,并且对应位置上的dp值加1后大于当前位置上的dp值,就更新当前位置上的dp值。最后,dp数组中的最大值就表示需要配备的最小系统数。
以下是一个可能的实现(使用Python语言):
```python
def missile_interception(nums):
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] > nums[i] and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
return max(dp)
# 示例输入
heights = [389, 207, 155, 300, 299, 170, 158, 65]
# 调用函数计算最小系统数
min_systems = missile_interception(heights)
print(min_systems)
```
输出结果为:
```
2
```
这表示需要配备两套导弹拦截系统才能拦截所有的导弹。
阅读全文