YACS20225月乙组——天平与砝码（二）

题目描述

小爱有一座天平，还有 n 个砝码，这些砝码的重量分别为 w_1,w_2​,…,wn​。称重时，砝码与物品可以放在同一边，也可以放在不同边。当砝码与物品放在同一边时，砝码起到了减法的效果。

请计算这些砝码，能够称出多少种重量。

输入：

3

1 4 10

输出：12

上海市计算机学会竞赛平台 | YACS

dp[i][j], 代表前 i 个砝码，能否凑成重量 j ；

因为题目中说到，砝码放到物体那一边，可以视作-，所以100个砝码实际上能有正负200个的情况

w[200] ; w[i+n]=-w[i]

初始条件是 dp[0][0]=true ; 前 0 个物品，凑成的质量是0，这个结果为真；

在实际计算中，先计算全部放+w的情况，即达到的最大重量；

然后在最大重量中，减去砝码，j-w[i]  

dp[i%2][j]=dp[(i+1)%2][j] ; 代表 对 i-1 取模2运算； (i-1+2)%2——>，dp[(i+1)%2][j] ; 

这里为啥要这么操作呢，是因为之前n=n*2 了！！所以这里要除以2，弄回去。

#include <iostream>
using namespace std;

bool dp[2][100001];
int n,w[201];

int main() {
    cin>>n;
    
    for (int i=1;i<=n;i++){
    	cin>>w[i];
    	w[i+n]=-w[i];
	}
	n=n*2;
	dp[0][0]=true;
	
	int sum_w=0;
	for (int i=1;i<=n;i++){
		if (w[i]>0)sum_w=sum_w+w[i];
		for (int j=0;j<=sum_w;j++){
			dp[i%2][j]=dp[(i+1)%2][j];
			if (j-w[i]>=0){
				dp[i%2][j]|=dp[(i+1)%2][j-w[i]];
			}
		}
		
	}
	int ans=0;
	for (int i=1;i<=sum_w;i++){
		ans+=dp[n%2][i];
	}
	cout<<ans;
    return 0;
}