dp
f[i][j]表示前i个砝码是否可以组成j重量,值为0/1
Tips
注意数组越界
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 110,M=100010;
int a[N],f[N][M];
int n,sum;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum+=a[i];
}
f[0][0]=1;//0不算答案但是要初始化一下,我们确实可以称出来0重量的,统计答案的时候从1重量开始
for(int i=1;i<=n;i++)
{
for(int j=0;j<=sum;j++)
{
f[i][j]=f[i-1][abs(j-a[i])]||f[i-1][min(sum,j+a[i])]||f[i-1][j];
//当sum=100000的时候,我们再加a[i]就爆数组第二维的上限了
}
}
int ans=0;
for(int i=1;i<=sum;i++)//0不算答案
{
if(f[n][i])ans++;
}
cout<<ans<<endl;
return 0;
}