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

本文主要是介绍【蓝桥杯】砝码称重 Python 实现与优化（练习系统满分）【第十二届省赛 A 组】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

之前实现了一个版本，但是总是过不了所有测试点，这几天突然想起来就又优化了一下。当然 dotcpp 上还是 91 分，但是官网练习系统都能过了（但是他给了你五秒啊喂……）
不过其实这个题本身就是比较中规中矩的 dp 问题啦，当然这个题不是放到 Python 组的，估计也有这方面的考虑吧～

import sys
# 第零个优化，快速输入输出，加不加都行。
input = sys.stdin.readline
print = sys.stdout.writen = 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]): continuedp[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")