试题 历届真题 砝码称重【第十二届】【省赛】【A组】
这道题的思路是动态规划，这也是我第一次接触动态规划算法。
我的理解如下：
以题目中给的测试样例来看，给定 3个砝码1 4 6，第一个砝码1必定能测出来，第二个砝码则是在1可测的基础上进行计算，可测重量有4，1+4，4-1三种。由此构建dp二维数组完成代码
80%解如下，最后两组数据超时，这个逻辑用c++跑可以全部通过，python运行太慢了…
n = int(input())
dp = [[0 for i in range(100000)] for i in range(n)]
str1 = input().split()
a = [] # 砝码数组
SUM = 0
for i in str1:
x = int(i) # 每个砝码重量
a.append(x)
SUM = SUM + x # 所有砝码能达到的最大重量
dp[0][a[0]] = 1 # 第一个砝码一定可以
# 第二个砝码开始动态规划
for i in range(1,n):
tmp = a[i] # 取一个砝码
for j in range(SUM):
dp[i][j+1] = dp[i-1]文章出处登录后可见！
已经登录？立即刷新
