Atcoder abc275F
题意：
给出一个长度为 \(n\) 的数组 \(A=(a_1,a_2,…,a_N)\)，问是否能通过删掉一些子段使剩下的数之和为 \(q\)。若可以，求出最小操作次数，否则输出 −1。
对于所有的 \(q\in[1,m]\) 回答这个问题，第 \(i\) 行输出 \(q=i\) 时的答案，每个问题互不影响。
\(1\leq n,m,a_i \leq 3000\)
这题一看这范围便觉得像是 dp。
状态：
我们用 \(f[i][j][k]\) 表示考虑了前 i 位，剩下的数字之和为 j ， 第 i 为是否选择的最小分段数。
转移方程：
\(f[i][j][0] \leftarrow \min(f[i - 1][j][0], f[i - 1][j][1])\)
这个容易想，因为当前这个数字选不选都不影响分段数，所以直接从 \(i - 1\) 转移过来。
\(f[i][j][1] \leftarrow \min(f[i - 1][j - a_i][0] + 1, f[i - 1][j - a_i][1])(j \geq a_i)\)
因为当前的数字选择了保留，那么若上一个数字未保留，分段数加一，而 \(j\) 要减去\(a_i\)。
递推基：
\(f[1][0][0] = 0\)
\(f[1][a_1][1] = 0(a_1 \leq m)\)
第一个数字比较特殊，若选择保留，不影响分段。此处注意： \(a_1 \leq m\)。若它特别大，会越界！
答案：
对于所有的 \(q\in[1,m]\)，答案：
\[\min(f[n][q][0] + 1,f[n][q][1]) \]可能有人有疑问，这里为什么要 +1？
是因为最后一个数字为保留，而在前面的计算中并为加上未保留的最后这一段(也就是被删掉的)。
OK，看看无注释code。
AcCode:
#include <bits/stdc++.h>
using namespace std;
const int N = 3001;
int n, m;
int a[N], dp[N][N][2];
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
memset(dp, 0x3f, sizeof dp);
if (a[1] <= m)
dp[1][a[1]][1] = 0;
dp[1][0][0] = 0;
for (int i = 2; i <= n; i++)
for (int j = 0; j <= m; j++) {
dp[i][j][0] = min(dp[i - 1][j][0], dp[i - 1][j][1]);
if (j >= a[i])
dp[i][j][1] = min(dp[i - 1][j - a[i]][0] + 1, dp[i - 1][j - a[i]][1]);
}
for (int i = 1; i <= m; i++) {
int ans = min(dp[n][i][0] + 1, dp[n][i][1]);
printf("%d\n", ans == 0x3f3f3f3f ? -1 : ans);
}
return 0;
}