lanqiao OJ 1447 砝码称重

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std ;
const int N = 110 , M = 1e5+10 ;
int f[N][M*2] ;//由于砝码重量可能越界  比如说在j = 99999 的时候 砝码的重量是10000 就越界了
               //取前i个砝码看可以称重j的情况是否可以
 
int a[N] ;
 
int main(){
  int n ; cin >> n ;
  for(int i = 1 ; i <= n ;i ++) cin >>a[i] ;
  f[0][0] = 1 ;
  for(int i = 1 ; i <= n ; i ++) {
    for(int j = 0 ; j <= 100000 ; j ++){
            //由三种情况转化而来
            //1.如果前n-1个砝码就可以做到那n个砝码也能做到
            //2.如果钱n-1个砝码可以称重j-w 则加上第n个砝码就可以称重j了
            //2.如果前n-1个砝码可以称重j+w 则放在对面减去第n个砝码就可以称重j了
      f[i][j] = f[i-1][abs(j-a[i])] | f[i-1][j] | f[i-1][j + a[i]] ;
    }
  }
  int ans = 0 ;
  for(int i = 1 ; i <= 100000; i ++) ans += f[n][i] ;
  cout << ans << endl; 
  return 0 ;
}