解题思路:动态规划,新加的砝码和目前所得的质量可以相加,相减(两种情况,新砝码减旧质量或旧质量减新质量),将所得的结果(大于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语言训练-求PI* (C语言代码)浏览:637 |
大家好,我是验题君浏览:601 |
C语言程序设计教程(第三版)课后习题6.2 (C语言代码)浏览:568 |
C二级辅导-等差数列 (C语言代码)浏览:803 |
The 3n + 1 problem (C语言代码)浏览:548 |
敲七 (C语言代码)浏览:2743 |
【偶数求和】 (C++代码)浏览:741 |
C语言程序设计教程(第三版)课后习题7.4 (C++代码)浏览:567 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:524 |
C语言训练-求具有abcd=(ab+cd)2性质的四位数 (C语言代码)浏览:933 |