题解 | #称砝码#

一个偏暴力的解法

思路

• 假设 a 质量的砝码有 a1 个，那么能够得到的不同的质量为 [0, a1] 个，每个质量的值分别为 [0, a*1, a*2...a*\a1]
• 同理，假设 b 质量的砝码有 b1 个，那么能够得到的不同的质量为 [0, b1] 个，每个质量的值分别为 [0, b*1, b*2...b*\b1]
• 如果仅存在 a 质量和 b 质量的砝码，在不考虑重复的情况下，取笛卡尔积能得到不同的质量 [0, a1 * b1] 个，每个不同的质量便是 [0+0, 0+b*1, 0+b*2...a*1+0, a*1+b*1, a*1+b*2...a*\a1+b*\b1]
• 直接取笛卡尔积存在重复的质量，需要在计算中，排除重复值

解法

• 当存在 n 个砝码时，首先需要计算出每个砝码自己组合可以得到的质量，即 [0, a*1, a*2...a*\a1], [0, b*1, b*2...b*\b1]...[0, n*1, n*2...n*\n1]
• 循环每一个列表，计算其和并存储，重复的略过。由于不清楚具体有多少种砝码，无法使用 for 循环层次嵌套，因此使用 while 循环

代码

n = int(input())
m = list(map(int, input().split()))
x = list(map(int, input().split()))

map_ = [[m[i] * j for j in range(x[i]+1)] for i in range(n)]
# print(map_)

if n == 1:
    print(len(map_[0]))
else:
    r = set(map_[0])  # 这里如果使用列表，会内存超限
    i = 1
    while i < n:
        r2 = set()
        for j in r:
            for k in map_[i]:
                r2.add(j + k)
        r |= r2
        i += 1
    print(len(set(r)))