ACM►DP

CF383D - Antimatter（DP）

题目链接：

题目链接

题目大意：

给出 N 给数，每个数可以取正或者取负，选取一个连续的区间，并设置好每个数的正负。问有多少种方式可以使得选取的数的和为 0 。

$1 \le N \le 1000$，所有数的和不会超过 10000。

题目分析：

定义 $dp[i][j]$ 的含义为前 i 个数进行选取，和为 j 的取法数量。

设 $a[i]$ 为第 i 个数的值，任意看出状态转移方程为：

$dp[i][j] = dp[i - 1][j - a[i]] + dp[i - 1][j + a[i]]$

如果我们只是设边界 $dp[0][0] = 1$ 的话，那么 $dp[i][0]$ 是第一个数为起始以第 i 个为为结尾的答案。

这里我们初始化所有的 $dp[i][0] = 1$，然后统计答案的时候减去初始化的 1 ，这样就代表以所有的位置为起点了。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1000 + 10;
const int MOD = 1000000007;
const int INF = 30000;
const int S = INF / 2;

typedef long long ll;

int data[MAX];
ll dp[MAX][INF];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", data + i);
    }
    for (int i = 0; i <= n; i++) dp[i][S] = 1;
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < INF; j++) {
            if (j > data[i]) dp[i][j] = (dp[i][j] + dp[i - 1][j - data[i]]) % MOD;
            if (j + data[i] < INF) dp[i][j] = (dp[i][j] + dp[i - 1][j + data[i]]) % MOD;
        }
        ans = (ans + dp[i][S] - 1) % MOD;
    }
    printf("%lld\n", ans);
}

解题过程：

想错了状态，然后只能思路整体就不对了emmmmm

以后长时间卡题考虑换个状态试试？