[Codeforces] 383D. Antimatter

題目連結:http://codeforces.com/problemset/problem/383/D

---

某種進階版的加減問題(?，原本的加減問題DP式大概長得像$dp[i][j] = dp[i-1][j+a_i]+dp[i-1][j-a_i]$之類的，而現在變成可以從任意時間點開始的話就除了原本的方法，還多了兩種:$dp[i][a_i]$跟$dp[i][-a_i]$

#include <bits/stdc++.h>
using namespace std;
const int C = 10000 + 5;
const int N = 1000 + 5;
const int MOD_BASE = 1000000007;
#define dp(i, j) way[(i)][(j)+C]

int way[N][2*C];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	for(int i=1;i<=n;i++){
		int x; cin>>x;
		for(int j=10000;j>=-10000;j--){
			if(j+x <= 10000) dp(i, j) += dp(i-1, j+x);
			if(j-x >= -10000) dp(i, j) += dp(i-1, j-x);

			dp(i, j) %= MOD_BASE;
		}
		dp(i, x)++;
		dp(i, -x)++;
	}
	int sum = 0;
	for(int i=1;i<=n;i++) sum = (sum+dp(i, 0))%MOD_BASE;
	cout<<sum<<'\n';
	return 0;
}