Python(贪心算法)问题 H: 导d拦截

Python(贪心算法)问题 H: 导d拦截,第1张

问题 H: 导d拦截

题目描述

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

输入导d依次飞来的高度(雷达给出的高度不大于30000的正整数)。
计算要拦截所有导d最小需要配备多少套这种导d拦截系统。

输入

n颗依次飞来的高度(1≤n≤1000)

输出

要拦截所有导d最小配备的系统数k

样例输入

389  207  155  300  299  170  158  65

样例输出

2

解答(贪心算法):

while True:
    try:
        s = list(map(int, input().split()))
        dp = [1 for i in range(len(s))]
        # 根据for循环的循环次数创建元素全为1的列表
        # 例如循环了8次则dp=[1, 1, 1, 1, 1, 1, 1, 1]
        for i in range(len(s)):
            for j in range(i):
                if s[j] < s[i]:  # s[i] 是当前的数字,j是动态的
                    dp[i] = max(dp[i], dp[j] + 1)
                    # 如果符合条件就在相应的i处实现元素值的增加
                    # 最终会出现一个增序数位置的数字递增效果
        print(max(dp))
    except:
        break

答案不唯一,必定有更加优化的解法欢迎分享

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/716079.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-25
下一篇 2022-04-25

发表评论

登录后才能评论

评论列表(0条)

保存