本文主要是介绍【蓝桥杯】 砝码称重 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")
这篇关于【蓝桥杯】 砝码称重 Python 实现与优化(练习系统满分)【第十二届省赛 A 组】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!