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;
}