acwing3417. 砝码称重

题目

题解

#include<iostream>
using namespace std;
const int N=110,M=200010, B=M/2;
int g[N];
bool f[N][M];
int n,m;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>g[i];
        m+=g[i];
    }
    f[0][B]=true;
    
    for(int i=1;i<=n;i++){
        for(int j=-m;j<=m;j++){
            f[i][j+B]=f[i-1][j+B];
            if(j-g[i]>=-m)f[i][j+B]|=f[i-1][j-g[i]+B];
            if(j+g[i]<=m)f[i][j+B]|=f[i-1][j+g[i]+B];
        }
    }
    
    int cnt=0;
    for(int j=1;j<=m;j++)if(f[n][j+B])cnt++;
    cout<<cnt<<endl;
    return 0;
}