首页 > 试题广场 >

拦截导弹

[编程题]拦截导弹

热度指数：4527 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

输入导弹依次飞来的高度（雷达给出的高度数据是不大于1000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

数据范围：导弹个数 n 满足 $1 \le n \le 1000 \$ ，导弹的高度 m 满足 $1 \le m \le 1000 \$

输入描述:

第一行输入一个正整数 n ，表示导弹的个数
第二行输入 n 个正整数，表示导弹的高度

输出描述:

输出一套拦截系统最多拦截多少导弹和最少要配备多少套导弹拦截系统两个正整数

示例1

输入

8
389 207 155 300 299 170 158 65

输出

6
2

算法知识视频讲解

C++

Spectre_

#include <iostream>
using namespace std;

int main() {
    int n, res1 = 1, res2 = 1;
    cin >> n;
    int arr[n], dp1[n], dp2[n];
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
        dp1[i] = 1;  // 最长下降子序列长度
        dp2[i] = 1;  // 最长上升子序列长度 = 最短下降子序列长度
    }
    // 时间复杂度O(N^2)，空间复杂度O(N)
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (arr[j] >= arr[i]) dp1[i] = max(dp1[i], dp1[j] + 1);
            else dp2[i] = max(dp2[i], dp2[j] + 1);
        }
        res1 = max(res1, dp1[i]);
        res2 = max(res2, dp2[i]);
    }
    cout << res1 << endl << res2;
    return 0;
}

发表于 2022-11-01 16:01:55 回复(0)

喜欢修勾的托尼也不容易

该题两问分开做的，第一个用了动规，max_num数组下标为i的元素表示第i个导弹是某个系统的第max_num[i]发炮弹，如果前i发炮弹中某个第j发炮弹的最低高度并且比当前炮弹高，那么第i发炮弹就在第j发炮弹之后进行拦截，即max_num[i]= max_num[j]+1。max_num中的最大值即为所求。

第二问，设置min_num数组表示最少需要len个拦截系统，min_num[i]表示第i个拦截系统的当前最低高度，遍历一遍炮弹的高度，如果有某个拦截系统的当前高度min_num[j]大于炮弹的高度，就让符合条件的拦截系统中最低高度的拦截系统拦截这个导弹，把min_num[i]等于炮弹高度，否则就新建一个拦截系统拦截这个导弹。

num = int(input()) s = input()
nums = s.split(" ")
for i in range(len(nums)):
    nums[i] = int(nums[i])
# print(nums)
max_num = []
ans_max = 0
for i, x in enumerate(nums):
    tmax = 0
    for j in range(0, i):
        if nums[j] >= x and max_num[j] > tmax:
            tmax = max_num[j]
    if ans_max < tmax + 1:
        ans_max = tmax + 1
    max_num.append(tmax + 1)
# print(max_num)
min_num = []


def solve(x: int):
    tmp = -1
    tmpy = 1001
    for i, y in enumerate(min_num):
        if y >= x and y < tmpy:
            tmpy = y
            tmp = i
    if tmp == -1:
        min_num.append(x)
    else:
        min_num[tmp] = x
    return


for x in nums:
    solve(x)
print(ans_max)
print(len(min_num))

发表于 2022-04-07 20:36:54 回复(0)

C++

元气少女李逵

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int b;
    vector<int> a;
    for(int i=0;i<n;i++)
    {
        cin>>b;
        a.push_back(b);
    }
    //下降子序列长度
    vector<int> dp(n+1,1);
    int maxnum=0;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(a[j]<=a[i])
            {
                dp[j]=max(dp[j],dp[i]+1);
                
            }
        }
        maxnum=max(maxnum,dp[i]);
    }
    //上升子序列长度
    vector<int> dp2(n+1,1);
    int maxnum2=0;
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(a[j]>a[i])
            {
                dp2[j]=max(dp2[j],dp2[i]+1);
                
            }
        }
        maxnum2=max(maxnum2,dp2[i]);
    }

    cout<<maxnum<<endl;
    cout<<maxnum2<<endl;
    return 0;
    
}

发表于 2022-04-11 11:13:48 回复(0)

C++

不过重头再来罢了

#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 1005;
int nums[maxn],dp1[maxn],dp2[maxn];

int main(){
	int n;
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> nums[i];
		dp1[i] = 1;
		dp2[i] = 1;
	}
	int ans1 = 0;
	int ans2 = 0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<i;j++){
			if(nums[j] < nums[i]){
				dp1[i] = max(dp1[i],dp1[j]+1);
			
			}
			if(nums[j] >= nums[i]){
				dp2[i] = max(dp2[i],dp2[j]+1);
			}
		}
		ans1 = max(ans1,dp1[i]);
		ans2 = max(ans2,dp2[i]);
	}
	cout << ans2 << endl;
	cout << ans1 << endl;
	return 0;
}

发表于 2022-03-10 17:24:17 回复(0)