https://www.luogu.com.cn/problem/P8742
输入 #1复制
3
1 4 6
输出 #1复制
10
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;
const LL N=2e7+10,M=2023;
const LL mod=100000007;
const double PI=3.1415926535;
#define endl '\n'
LL n,sum=0,w[N],f[101][100001];
int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
LL T=1;
//cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>w[i];
sum+=w[i];
}
for(int i=1;i<=n;i++)
{
for(int j=sum;j;j--)//我们最多是只能凑到sum，但是凑不到比0小的
{
if(j==w[i]) f[i][j]=1;//如果当前刚好等于这个数，我直接躺赢了
else if(f[i-1][j]) f[i][j]=1;//如果之前已经凑到过这个数，我又躺赢了
else if(f[i-1][j+w[i]]) f[i][j]=1;//如果之前的基础上加上当前这个数字凑到过，说明我只需要倒退一步就又有了，再次躺赢
else if(f[i-1][abs(j-w[i])]) f[i][j]=1;//如果之前的基础上我只需要加上这一步就有，我也赢了（此处需要了解，必须是>0的数，否则影响计算结果）
}
}
LL ans=0;
for(int i=1;i<=sum;i++)
{
if(f[n][i]) ans++;
}
cout<<ans<<endl;
}
return 0;
}