首页 > 试题广场 >

拦截导弹

[编程题]拦截导弹

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

某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。

输入描述:

每组输入有两行，
第一行，输入雷达捕捉到的敌国导弹的数量k（k<=25），
第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。

输出描述:

每组输出只有一行，包含一个整数，表示最多能拦截多少枚导弹。

示例1

输入

8
300 207 155 300 299 170 158 65

输出

算法知识视频讲解

Python

TimeMac

while True:
    try:
        num = int(input())
        digitsList = list(map(int,input().split()))
        dp = [1]*num
        for i in range(num):
            for j in range(i):
                if digitsList[i] <= digitsList[j]:
                    dp[i] = max(dp[i],1+dp[j])
        print(max(dp))
        print(dp)
    except Exception:
        break

编辑于 2018-10-01 15:19:38 回复(0)

Python

Benjaminz

#coding=utf-8
#动态规划，找从右边开始最长的升序排列
while True:
	try:
		n=input()
		lis=list(raw_input().split())
		lis=[int(i) for i in lis]
		dp=[1 for i in range(n)]
		for i in range(n-1,-1,-1):
			for j in range(i+1,n):
				if lis[i]>=lis[j]:
					dp[i]=max(dp[i],dp[j]+1)
		print max(dp)
	except:
		break

发表于 2017-08-07 11:12:48 回复(0)