砝码称重(动态规划c++实现)

题目

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

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

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

输入

输入的第一行包含一个整数 N。

第二行包含 N个整数：W1,W2,W3,⋅⋅⋅,WN。

输出

输出一个整数代表答案。

样例

输入样例：
3
1 4 6
输出样例：
10

代码

#include<iostream>
#include<cmath>
using namespace std;
const int N = 110,M=2e5+10,B = M/2;
int n;
int q[N];
bool f[N][M];
bool st[M];

int main(){
    scanf("%d",&n);
    int sum = 0;
    for(int i=1;i<=n;i++) {
        scanf("%d",&q[i]);
        sum+=q[i];
    }
    f[0][B] = true;
    int res = 0;
    for(int i=1;i<=n;i++){
        for(int j=-sum;j<=sum;j++){
            f[i][j+B] |= f[i-1][j+B];
            if(j-q[i]>=-sum) f[i][j+B] |= f[i-1][j-q[i]+B];
            if(j+q[i]<=sum) f[i][j+B] |= f[i-1][j+q[i]+B];
        }
    }
    for(int i=1;i<=sum;i++) if(f[n][i+B]) res++;
    printf("%d",res);
}