题目描述
你有一架天平和N 个砝码，这N 个砝码重量依次是W1, W2, ... , WN。
请你计算一共可以称出多少种不同的重量？
注意砝码可以放在天平两边。
输入格式
输入的第一行包含一个整数N。
第二行包含N 个整数：W1, W2, W3, ... , WN。
对于50% 的评测用例，1 ≤ N?≤?15。
对于所有评测用例，1?≤?N?≤?100，N 个砝码总重不超过100000。
?
输出格式
输出一个整数代表答案。
输入样例?复制
3
1 4 6
输出样例?复制
10
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const int N=110,M=200010,B=M/2;
int n,m;
int w[N];
bool f[N][M];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>w[i];
m+=w[i];
}
f[0][B]=true;
for(int i=1;i<=n;i++)
{
for(int j=-m;j<=m;j++)
{
f[i][j+B]=f[i-1][j+B];//不选
if(j-w[i]>=-m)f[i][j+B]|=f[i-1][j-w[i]+B];
if(j+w[i]<=m)f[i][j+B]|=f[i-1][j+w[i]+B];
}
}
int res=0;
for(int j=1;j<=m;j++)
{
if(f[n][j+B])
res++;
}
cout<<res;
return 0;
}
?
|