AcWing 3417. 砝码称重
原题链接
中等
作者:
a_little
,
2024-04-05 17:16:00
,
所有人可见
,
阅读 5
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110,M=2e5+10,B=M/2;
bool f[N][M];
int w[N];
int 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 i=1;i<=m;i++){
if(f[n][i+B]) res++;
}
cout<<res;
return 0;
}