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;

}