原题链接:金明的预算方案
解题思路:
注意事项:
参考代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | p,n = map ( int , input ().split()) lis = [] l = [] p / / = 10 for i in range (n): a,b,c = map ( int , input ().split()) a / / = 10 if c = = 0 : lis.append([a,a * b]) else : l.append([a,a * b,c]) lt = [[] for i in range ( len (lis))] for i in l: lt[i[ 2 ] - 1 ].append(i) ls = [[i] for i in lis] for i in range ( len (lis)): if len (lt[i]) = = 1 : s = [lt[i][ 0 ][j] + ls[i][ 0 ][j] for j in range ( 2 )] ls[i].append(s) if len (lt[i]) = = 2 : s = [lt[i][ 0 ][j] + ls[i][ 0 ][j] for j in range ( 2 )] ls[i].append(s) s = [lt[i][ 1 ][j] + ls[i][ 0 ][j] for j in range ( 2 )] ls[i].append(s) s = [lt[i][ 1 ][j] + ls[i][ 0 ][j] + lt[i][ 0 ][j] for j in range ( 2 )] ls[i].append(s) li = [] for i in ls: li.append( len (i)) dp = [ 0 for i in range (p + 1 )] for num in range ( len (ls)): for pri in range (p, - 1 , - 1 ): for i in range (li[num]): if pri > = ls[num][i][ 0 ]: dp[pri] = max (dp[pri],ls[num][i][ 1 ] + dp[pri - ls[num][i][ 0 ]]) print (dp[ - 1 ] * 10 ) |
9.9 分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复