Luogu4141 消失之物

tony102

2021 年 01 月 26 日

1505 次浏览

暂无评论

599字数

题解

[Link](https://www.luogu.com.cn/problem/P4141)

是真的需要补一补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

```cpp
#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;
}
```

最后修改：2021 年 09 月 04 日