D
e
s
c
r
i
p
t
i
o
n
Description
Description
小C为了试验小X，便为物竞的小X出了一道物理相关的题：现在给出n个质量的砝码，问小X能称出多少种质量的物品，可是总有好事者想要破坏，于是乎，n达到了500，远远超出了小X能够承受的范围，锲而不舍的他决定寻求你们的帮助。
I
n
p
u
t
Input
Input
第一行输入一个的正整数N 以下N行每行一个不超过200的正整数，依次表示每个砝码的质量。
O
u
t
p
u
t
Output
Output
输出总共能称出多少种不同质量的物品。
S
a
m
p
l
e
Sample
Sample
I
n
p
u
t
Input
Input
3
1
3
9
S
a
m
p
l
e
Sample
Sample
O
u
t
p
u
t
Output
Output
13
E
x
p
l
a
i
n
Explain
Explain
天平有两边，两边均可放。
T
r
a
i
n
Train
Train
o
f
of
of
T
h
o
u
g
h
t
Thought
Thought
设
f
[
i
]
[
j
]
f[i][j]
f[i][j]为前i个物品能否有重量j 所以若当前重量可以，那么左右（任意）加上一个砝码称出来的重量也是可以的 得：
f
[
i
]
[
j
]
=
f
[
i
]
[
j
−
a
[
i
]
]
=
f
[
i
]
[
j
+
a
[
i
]
]
=
t
r
u
e
f[i][j]=f[i][j-a[i]]=f[i][j+a[i]]=true
f[i][j]=f[i][j−a[i]]=f[i][j+a[i]]=true 最后再统计一共有多少个就可以了 因为可以放两边，所以要注意负数
C
o
d
e
Code
Code
#include<cstdio>
#include<iostream>
using namespace std
;
int ans
,n
,a
[1001];
bool f
[1005][40005];
int main()
{
scanf("%d",&n
);
f
[0][20000]=1;
for (int i
=1; i
<=n
; ++i
)
scanf("%d",&a
[i
]);
for (int i
=1; i
<=n
; ++i
)
for (int j
=0; j
<=40000; ++j
)
{
if (f
[i
-1][j
])
f
[i
][j
+a
[i
]]=f
[i
][j
-a
[i
]]=f
[i
][j
]=true;
}
for (int j
=20001; j
<=40000; ++j
)
if (f
[n
][j
]) ans
++;
printf("%d",ans
);
}
