Codeforces 383 D. Antimatter（DP）

本文主要是介绍Codeforces 383 D. Antimatter（DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Iahub accidentally discovered a secret lab. He found there n devices ordered in a line, numbered from 1 to n from left to right. Each device i (1 ≤ i ≤ n) can create either ai units of matter or ai units of antimatter.

Iahub wants to choose some contiguous subarray of devices in the lab, specify the production mode for each of them (produce matter or antimatter) and finally take a photo of it. However he will be successful only if the amounts of matter and antimatter produced in the selected subarray will be the same (otherwise there would be overflowing matter or antimatter in the photo).

You are requested to compute the number of different ways Iahub can successful take a photo. A photo is different than another if it represents another subarray, or if at least one device of the subarray is set to produce matter in one of the photos and antimatter in the other one.

Input
The first line contains an integer n (1 ≤ n ≤ 1000). The second line contains n integers a1, a2, …, an (1 ≤ ai ≤ 1000).

The sum a1 + a2 + … + an will be less than or equal to 10000.

Output
Output a single integer, the number of ways Iahub can take a photo, modulo 1000000007 (109 + 7).

Examples
inputCopy
4
1 1 1 1
outputCopy
12
Note
The possible photos are [1+, 2-], [1-, 2+], [2+, 3-], [2-, 3+], [3+, 4-], [3-, 4+], [1+, 2+, 3-, 4-], [1+, 2-, 3+, 4-], [1+, 2-, 3-, 4+], [1-, 2+, 3+, 4-], [1-, 2+, 3-, 4+] and [1-, 2-, 3+, 4+], where “i+” means that the i-th element produces matter, and “i-” means that the i-th element produces antimatter.

题意：
取一段连续数，每个数可以是原数也可以是其相反数。求多少种取法使得所取的和为0。

思路：
定义 $d p [i] [j + 10000]$ 为前 $i$ 个数后缀和为 $j$ 的方案数。
因为可能出现负数，所以要加上10000以免出现负数，
转移那就更简单了，要么取前面的后缀，要么不取，所以是：
$d p [i] [a [i] + 10000] = 1 ， d p [i] [- a [i] + 10000] = 1$
$d p [i] [j + a [i] + 10000] + = d p [i] [j + 10000]$
$d p [i] [j - a [i] + 10000] + = d p [i] [j + 10000]$

感觉这种DP套路题做的多了还是很水。贪心就不一样了，随便想的的A了，感觉是对的反而过不了巴拉巴拉。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;typedef long long ll;
const int maxn = 1e4 + 7;
const int mod = 1e9 + 7;ll dp[1005][maxn * 2];
int a[1005];int main() {int n;scanf("%d",&n);for(int i = 1;i <= n;i++) scanf("%d",&a[i]);ll ans = 0;for(int i = 1;i <= n;i++) {for(int j = -10000;j + a[i] <= 10000;j++) {int num1 = j + a[i] + 10000,num2 = j + 10000;dp[i][num1] = (dp[i][num1] + dp[i - 1][num2]) % mod;}for(int j = 10000;j - a[i] >= -10000;j--) {int num1 = j - a[i] + 10000,num2 = j + 10000;dp[i][num1] = (dp[i][num1] + dp[i - 1][num2]) % mod;}dp[i][a[i] + 10000] = (dp[i][a[i] + 10000] + 1) % mod;dp[i][-a[i] + 10000] = (dp[i][-a[i] + 10000] + 1) % mod;ans = (ans + dp[i][10000]) % mod;}printf("%lld\n",ans);return 0;
}