解题思路:动态规划,新加的砝码和目前所得的质量可以相加,相减(两种情况,新砝码减旧质量或旧质量减新质量),将所得的结果(大于0)存入dp,供下一次使用,
注意事项:中间要专门设一个列表,用于存储新称的重量,不能直接存入dp,用set集合可以比list速度快
参考代码:
n = int(input())
arr = list(map(int,input().split()))
dp = set()
dp.add(arr[0])
for i in range(1,n):
t = set()
if arr[i] not in dp:
t.add(arr[i])
for j in dp:
if arr[i]+j not in dp:
t.add(arr[i]+j)
if arr[i]-j not in dp and arr[i]-j>0:
t.add(arr[i]-j)
if j-arr[i] not in dp and j-arr[i]>0:
t.add(j-arr[i])
dp = dp.union(t)
print(len(dp))
0.0分
1 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复