是真的需要补一补dp
Sol
首先还是可以想到经典的背包计数。那么就是设 $f[i][j]$ 表示放前$i$个物品,体积为$j$的方案数。转移非常简单,$f[i][j] = f[i-1][j] + f[i - 1][j - w[i]]$ 。边界条件$f[0][0] = 1$
现在我们要考虑不放第$i$个物品体积为$x$的方案数,设这个为$g[i][j]$。那么不放$i$可以由两种情况。假如当前的体积$j < w[i]$,那么我们怎么也不可能放第$i$个物品,$g[i][j] = f[i][j]$ 。假如当前的体积$j \geq w[i]$, 那么方案数就是所有物品放出体积为$j$的背包的方案数减去不放第$i$个物品凑出体积为$j-w[i]$的背包的方案数
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int SIZE = 2e3 + 5;
int n, m;
int w[SIZE], f[SIZE][SIZE], c[SIZE][SIZE];
namespace ae86 {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
return *s++;
}
inline int read() {
int a = 0, b = 1, c = fetch();
while (!isdigit(c))b ^= c == '-', c = fetch();
while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
return b ? a : -a;
}
}
using ae86::read;
signed main() {
// freopen("code.in", "r", stdin);
n = read(), m = read();
for (int i = 1; i <= n; ++ i) w[i] = read();
f[0][0] = 1;
for (int i = 1; i <= n; ++ i) {
for (int j = 0; j <= m; ++ j) {
f[i][j] = (f[i][j] + f[i - 1][j]) % 10;
if (j >= w[i]) f[i][j] = (f[i][j] + f[i - 1][j - w[i]]) % 10;
}
}
for (int i = 0; i <= m; ++ i) c[0][i] = 1;
for (int i = 1; i <= n; ++ i) {
for (int j = 0; j <= m; ++ j) {
if (j < w[i]) c[i][j] = (f[n][j] + c[i][j]) % 10;
else c[i][j] = (((c[i][j] + f[n][j]) % 10) - c[i][j - w[i]] + 10) % 10;
}
}
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j) printf("%lld", (c[i][j] + 10) % 10);
puts("");
}
return 0;
}