[Acwing|蓝桥杯] 3417. 砝码称重 背包求方案数

前言

传送门 :

思路

如果只考虑放一边可以组合出多少种类的话,那么显然是背包组合方案数

但是这里是可以放两边的,也就是在转移的时候会出现一个 j − a [ i ] j-a[i] j−a[i]有可能会出现负数

的情况。但是仔细想想,如果放左边无非就让右边的减少了重量,因此转移的时候

可以添加 a b s ( j − a [ i ] ) abs(j-a[i]) abs(j−a[i])

状态表示 : f [ i ] [ j ] f[i][j] f[i][j] 前 i i i个物品里面选,体积是 j j j的方案数

状态计算 : f [ i ] [ j ] + = f [ i − 1 ] [ j ] + f [ i − 1 ] [ j + a [ i ] ] + f [ i − 1 ] [ a b s ( j − a [ i ] ) ] f[i][j] +=f[i-1][j]+f[i-1][j+a[i]]+f[i-1][abs(j-a[i])] f[i][j]+=f[i−1][j]+f[i−1][j+a[i]]+f[i−1][abs(j−a[i])]

特别注意的是,我们将负数的情况转为正数,保守情况下应该开 2 e 5 2e5 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>a[i];
		sum+=a[i];
	}
	
	f[0][0] = 1;
	for(int i=1;i