题解 | #称砝码#

n = int(input())
weights = list(map(int, input().split()))
numbers = list(map(int, input().split()))
hashset = set()


# def dfs(now, sum):
#     if now == n:
#         hashset.add(sum)
#         # print(now, sum)
#         return
#     for i in range(numbers[now]+1):
#         dfs(now + 1, sum + i * weights[now])


# dfs(0, 0)
# print(len(hashset))

# 动态规划
ans = {0}
for i in range(n):
    w = weights[i]
    for num in range(numbers[i]):
        tmp = ans.copy()
        for x in tmp:
            ans.add(x + w)

        # print(w, num, ans)
print(len(ans))

一开始用了暴力法，果断超时了。后来发现动态规划，假设我有一堆砝码和它们能称出来的所有重量，现在往里面加入一个砝码，那么能称的所有重量就是 `S := set(w + s for s in S)`，这就得到转移方程。

注意我们要模拟每次加一个砝码的过程，如果完全不加那就是初始状态，每次加一个`w`，一共加`num`次，即可。