前言
思路
如果只考虑放一边可以组合出多少种类的话,那么显然是背包组合方案数
但是这里是可以放两边的,也就是在转移的时候会出现一个$j-a[i]$有可能会出现负数
的情况。但是仔细想想,如果放左边无非就让右边的减少了重量,因此转移的时候
可以添加$abs(j-a[i])$
状态表示 :
$f[i][j]$ 前$i$个物品里面选,体积是$j$的方案数
状态计算 :
$f[i][j] +=f[i-1][j]+f[i-1][j+a[i]]+f[i-1][abs(j-a[i])]$
特别注意的是,我们将负数的情况转为正数,保守情况下应该开$2e5$
CODE
const int N = 1e5+10;
int f[110][N];
int a[N];
int n,sum;
void solve()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
f[0][0] = 1;
for(int i=1;i<=n;i++){
for(int j = 0 ;j<=sum;j++){
f[i][j] =
f[i-1][j] + f[i-1][j+a[i]]+f[i-1][abs(j-a[i])];
}
}
ll ans = 0 ;
for(int i=1;i<=sum;i++){
if(f[n][i])++ans;
}
cout<<ans<<endl;
}