[TIOJ] 1508. 加減問題

題目連結:http://tioj.infor.org/problems/1508

---

類背包問題，開一條長度為該序列總和的array，然後每次加入一個數都$O(sum)$跑過去比對新的數加進去後可以產生甚麼數，複雜度$O(n \Sigma n)$

#include <cstdio>
#include <bitset>

using std::bitset;

inline long ABS(long a){
  return a<0?-a:a;
}

int main() {
    int m,n;
    scanf("%d%d",&m,&n);
    while(m--){
      int arr[100 + 10];
      long sum=0;
      for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
        sum+=arr[i];
      }
      bitset<100000 + 10> b;
      b[0]=1;
      for(int i=0;i<n;i++){
        bitset<100000 + 10>temp;
        for(int j=0;j<=sum;j++){
          if(b[j]){
            temp[j+arr[i]]=1;
            temp[ABS(j-arr[i])]=1;
          }
        }
        b=temp;
      }
      puts(b[0]?"Yes":"No");
    }
}