感觉上算是个状压DP吧, 但是没想到什么可以有效的存储1e6位的数, 最后还是选择了数组

假设有一个长度为1e6的数组, 表示可以称出的重量, 那么每多一个砝码(重量为k), 那么对于任何一个已经可以称出的重量(i), 可以组合得到 i-k, k-i, i+k这三种重量

我们只需要维护这个数组即可

#include "iostream"
using namespace std;
const int N = 1e6 + 7;
int W[N] = {1};
signed main(){
    int n; cin >> n; while(n--) {
        int t; cin >> t;
        for(int i = 0; i < N; ++ i){
            // 为了节省空间, 用-1表示在大于i的, 1表示小于等于i的, 0表示无法称出的
            if(W[i] == 1) {
                // i-t的情况
                if(i > t) W[i - t] = 1;
                // t-i的情况
                if(t > i + i && W[t - i] != 1) W[t - i] = -1;
                if(t - i > 0 && W[t - i] != -1) W[t - i] = 1;
                // i+t的情况
                if(i + t < N && W[i + t] != 1) W[i + t] = -1;
            }
            if(W[i] == -1) W[i] = 1;
        }
    }
    int cnt = 0; for(int i = 1; i < N; ++ i) cnt += W[i]; cout << cnt << endl;
}