妙先生


私信TA

用户名:uq_57083779177

访问量:24596

签 名:

妙啊!

等  级
排  名 234
经  验 5954
参赛次数 0
文章发表 73
年  龄 0
在职情况 学生
学  校
专  业

  自我简介:

解题思路:
    主要用到动态规划用列表记录每个导弹连续下降或上升的个数,并且每个导弹的下降或上升个数只和前面导弹的高度有关,不用担心后面,这是贪心。

    求最大下降序列对应最多拦截的导弹。

    求最大上升序列对应几套装备。

    详情解析看这

    
参考代码:

H = list(map(int,input().split()))
n,maxVal,minVal = len(H),0,0
dp = [0 for _ in range(n)]
#最长不上升序列问题  (最多能拦截导弹数)
for i in range(n):
    dp[i] = 1
    for j in range(i):
        if H[i]<=H[j] and dp[i]<(dp[j]+1):
            dp[i] = dp[j] + 1
    if maxVal < dp[i]:
        maxVal=dp[i]
#最长不下降序列问题  (最少需要几套装备)
for i in range(n):
    dp[i] = 1
    for j in range(i):
        if H[i] > H[j] and dp[i]<(dp[j]+1):
            dp[i] = dp[j] + 1
    if minVal < dp[i]:
        minVal = dp[i]
print(maxVal)
print(minVal)


 

0.0分

7 人评分

  评论区