AtCoder Regular Contest 180 C. Subsequence and Prefix Sum （dp好题 辅助数组）
题目
给你一个长度为 N（N<=10）的整数序列 A=(A1,A2,⋯,AN)。
你要准确地执行一次下面的操作：
- 选择 A 的一个非空子序列(不一定连续)，并用它的累积和替换。
- 更精确地说，首先选择一个索引序列 (i1,i2,⋯,ik) ，使得 1≤i1<i2<⋯<ik≤N
- 序列 k ( 1≤k≤N)的长度可以自由选择。
- 然后，对于每个 j ( 1≤j≤k)，用 ∑1≤x≤jAix 替换 Aij 的值。
- 所有选择的索引同时进行替换。
求操作后 A 的可能序列数。
思路来源
洛谷题解
题解
由于子序列当前和为0的时候，选ai和不选ai实际是一种方案，所以把这种情况择出来，
选ai的时候转移进g数组，不选ai的时候忽略，
那么对于0 1 1 2来说，
要么只选了0，还是在f里，
要么选了0，选了一个1，这种情况和只选0是一样的，不在f里统计，在g里统计一次
要么选了0，选了一个1，选了1个2，这种情况仍在f里统计，也只统计一次，从g转移回来即可
做法挺巧妙的，g实际是一个辅助数组，dp还是很锻炼思维的
代码
#include <algorithm>
#include <atcoder/modint>
#include <iostream>using namespace std;
using LL = atcoder::modint1000000007;const int kN = 101, kV = 11;int n, a[kN];
LL _f[kN][kN * kV * 2], *f[kN];
LL _g[kN * kV * 2], *g = _g + kN * kV;int main() {ios::sync_with_stdio(0), cin.tie(0);cin >> n;for (int i = 1; i <= n; ++i) {cin >> a[i];}for (int i = 0; i <= n + 1; ++i) {f[i] = _f[i] + kN * kV;}f[0][0] = 1;int l = 0, r = 0;for (int i = 1; i <= n; ++i) {for (int j = l; j <= r; ++j) {f[i][j] += f[i - 1][j];if (j) {f[i][j + a[i]] += f[i - 1][j] + g[j];}}g[a[i]] = f[i - 1][0];l += min(0, a[i]), r += max(0, a[i]);}LL ans = 0;for (int i = l; i <= r; ++i) {ans += f[n][i];}cout << ans.val();return 0;
}