解题思路:
主要用到动态规划用列表记录每个导弹连续下降或上升的个数,并且每个导弹的下降或上升个数只和前面导弹的高度有关,不用担心后面,这是贪心。
求最大下降序列对应最多拦截的导弹。
求最大上升序列对应几套装备。
参考代码:
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 人评分
WU-输出正反三角形 (C++代码)浏览:1018 |
C语言程序设计教程(第三版)课后习题6.2 (C语言代码)浏览:703 |
【计算两点间的距离】 (C语言代码)浏览:1474 |
【计算直线的交点数】 (C语言代码)浏览:1443 |
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:664 |
2004年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:583 |
数组与指针的问题浏览:716 |
C语言程序设计教程(第三版)课后习题9.6 (C语言代码)浏览:579 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:511 |
C语言程序设计教程(第三版)课后习题12.6 (C语言代码)浏览:650 |