砝码称重

题目描述：

你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1,W2,···,WN。

请你计算一共可以称出多少种不同的正整数重量？

注意砝码可以放在天平两边。

思路：

值域很小，才1e5，所以可以考虑01背包

我们把重量为w的砝码放左边看作-w,放右边看作+w

那状态转移方程就是：

dp[i][j] = dp[i - 1][j] | dp[i - 1][j - w] | dp[i - 1][j + w]

有一个问题是dp[i] [j - w]可能会访问到负下标

我们从定义的角度上来分析一下，j-w<0相当于在左边的天平上放上了w-j的砝码，也就说如果我们能构造出w-j,也就能构造出j-w的重量

那我们就可以加一个绝对值abs(j-w)即可

为了省空间，我们再用一个滚动数组

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
int tr[MAX];
bool dp[105][MAX];

void work(){
    cin >> n;
    int sum = 0;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];sum += tr[i];
    }
    dp[0][0] = 1;
    for(int i = 1; i <= n; ++i){
        for(int j = 0; j <= sum; ++j){
            dp[i][j] = (dp[i - 1][j]
                        | dp[i - 1][j + tr[i]]
                        | dp[i - 1][abs(j - tr[i])]);
        }
    }
    int ans = 0;
    for(int i = 1; i <= sum; ++i){
        if(dp[n][i])++ans;
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}