AcWing 3417. 砝码称重
原题链接
中等
作者:
最后五分钟
,
2024-03-28 21:00:26
,
所有人可见
,
阅读 4
#include<bits/stdc++.h>
#define LL long long
#define x first
#define y second
#define de(x) cout<<#x<<" = "<<x<<" "
#define deg(x) cout<<#x<<" = "<<x<<endl
using namespace std;
const int N=210,M=2e5+10;
int v[N];
typedef pair<int,int> PII;
int f[N][M];
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i];
v[i+n]=-v[i];
}
f[0][0]=1;
for(int i=1;i<=2*n;i++)
for(int j=0;j<=1e5;j++)
{
f[i][j]=f[i-1][j];
if(j-v[i]>=0)f[i][j]=max(f[i][j],f[i-1][j-v[i]]);
}
int res=0;
for(int i=1;i<=1e5;i++)
if(f[2*n][i])
{
res++;
}
cout<<res<<endl;
return 0;
}