3417. 砝码称重
摘要
Title: 3417. 砝码称重
Tag: 背包
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
3417. 砝码称重
-
题意
你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN。
请你计算一共可以称出多少种不同的正整数重量？
注意砝码可以放在天平两边。 -
思路
有限制的选择问题——背包问题，用背包的i,j定义去分析这个题
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34'''
Author: NEFU AB-IN
Date: 2022-03-21 16:55:42
FilePath: \ACM\Acwing\3420.py
LastEditTime: 2022-03-21 16:55:42
'''
N = 150
M = int(2e5 + 10)
B = M // 2 #由于j存在负数，所以给所有j加上偏移量
dp = [[0] * M for _ in range(N)]
n = int(input())
w = list(map(int, input().split()))
w = [0, *w]
m = sum(w)
dp[0][B] = 1
for i in range(1, n + 1):
for j in range(-m, m + 1):
dp[i][j + B] = dp[i - 1][j + B]
if j - w[i] >= -m:
dp[i][j + B] |= dp[i - 1][j - w[i] + B]
if j + w[i] <= m:
dp[i][j + B] |= dp[i - 1][j + w[i] + B]
ans = 0
for j in range(1, m + 1):
if dp[n][j + B]:
ans += 1
print(ans)
