【蓝桥杯】 砝码称重 Python 实现与优化（练习系统满分）【第十二届省赛 A 组】

之前实现了一个版本，但是总是过不了所有测试点，这几天突然想起来就又优化了一下。

当然 dotcpp 上还是 91 分，但是官网练习系统都能过了（但是他给了你五秒啊喂……）
不过其实这个题本身就是比较中规中矩的 dp 问题啦，当然这个题不是放到 Python 组的，估计也有这方面的考虑吧～

import sys
# 第零个优化，快速输入输出，加不加都行。


input = sys.stdin.readline
print = sys.stdout.write

n = int(input())
w = [0, *map(int, input().split())]
MAXN = sum(w) + 1
# 第一个优化，所有物品能组成的最大状态就是他们的总和（这里也可以用字典实现啦）
dp = [[False] * MAXN for _ in range(n + 1)]
# 另外要注意的是这个题是没法用滚动数组的，这和状态的继承有关。


dp[0][0] = True
# 第二个优化，结果使用集合记录能称出的重量。


res = set()
for i in range(1, n + 1):
    for j in range(MAXN):
        dp[i][j] = dp[i - 1][j]
        # 优化三，如果 i-1 个 砝码能称出来这里会继承到。


        # 但是这个状态在之前已经加到我们的值里了，所以直接跳过
        # 这样还避免了 j = 0 的情况～
        if (dp[i][j]): continue
        dp[i][j] |= dp[i - 1][abs(j - w[i])]
        if (j + w[i] < MAXN):
            dp[i][j] |= dp[i - 1][j + w[i]]
        # 记录称出的结果
        if (dp[i][j]): res.add(j)
# 前面使用 stdout.write 替代了 print 所以这里要手动加换行符
print(str(len(res)) + "\n")