大军


私信TA

用户名:uq_38638415728

访问量:103

签 名:

等  级
排  名 32517
经  验 452
参赛次数 0
文章发表 1
年  龄 0
在职情况 学生
学  校
专  业

  自我简介:

解题思路:动态规划,新加的砝码和目前所得的质量可以相加,相减(两种情况,新砝码减旧质量或旧质量减新质量),将所得的结果(大于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 人评分

  评论区

  • «
  • »