Note - O(nV) 求只关心一个位置的 01 背包
给定序列 \(a_{1\sim n}\)，其中 \(0\le a_i\le m\)。
给定 \(V\)。询问是否存在 \(S\subseteq \{1, 2, \cdots, n\}\) 满足 \(\sum\limits_{i\in S} a_i = V\)。\(n\ge 1, m, V\ge 0, n, m\le 10^4, V\le nm\)。
先咕一下，贴个代码（
#include<bits/stdc++.h>
const int maxn = 1e4 + 10, maxm = 2e4 + 10, BASE = 1e4 + 2;
int a[maxn], F[maxm], G[maxm];
int main() {
int n, m, V; scanf("%d%d%d", &n, &m, &V);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
int p = 0;
while (p < n && V >= a[p + 1]) V -= a[++p];
if (p == n)
return printf("%d\n", ! V), 0;
int *f = F + BASE, *g = G + BASE;
f[V] = p + 1;
for (int i = p + 1; i <= n; i++) {
memcpy(g - m, f - m, sizeof(int) * (m + m + 1));
for (int j = m; j - a[i] >= -m; j--)
f[j - a[i]] = std::max(f[j - a[i]], g[j]);
for (int j = -m; j <= m; j++)
for (int k = std::max(g[j], 1); k < f[j]; k++)
if (j + a[k] <= m)
f[j + a[k]] = std::max(f[j + a[k]], k);
}
printf("%d\n", f[0] > 0);
return 0;
}