第三次比赛E题.砝码

//01背包变形(三类情况，不增不减，增砝码，减砝码)
include<bits/stdc++.h>
using namespace std;
const int N=110,M=200010,b=M/2;
int v[N],f[N][M];
int main()
{
int n,sum;
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&v[i]),sum+=v[i];
f[0][b]=true;
for(int i=1;i<=n;i++)
for(int j=sum;j;j--)
{
if(j==v[i])f[i][j]=1;
else if(f[i-1][j])f[i][j]=1;
else if(f[i-1][abs(j-v[i])])f[i][j]=1;
else if(f[i-1][j+v[i]])f[i][j]=1;
}
int res=0;
for(int i=1;i<=sum;i++)if(f[n][i])res++;
cout<<res<<endl;
return 0;
}
//或者
include<bits/stdc++.h>
using namespace std;
const int N=110,M=200010,b=M/2;
int v[N];
bool f[N][M];
int main()
{
int n,sum;
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&v[i]),sum+=v[i];
f[0][b]=true;
for(int i=1;i<=n;i++)
for(int j=-sum;j<=sum;j++)
{
f[i][j+b]=f[i-1][j+b];
if(j-v[i]>=-sum)f[i][j+b]|=f[i-1][j-v[i]+b];
if(j+v[i]<=sum)f[i][j+b]|=f[i-1][j+v[i]+b];
}
int res=0;
for(int i=1;i<=sum;i++)if(f[n][i+b])res++;
cout<<res<<endl;
return 0;
}