自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 21:42:06，当前版本为作者最后更新于2023-04-05 12:52:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

本题题目描述简短，不多赘述。

思路

由于是组合计数问题，需要考虑到纸币种类这个阶段以及每次加入一种新纸币产生的贡献。

所以使用状态 $f_{i,j}$ 表示只用前 $i$ 种纸币凑到金额 $j$ 的方案数。

于是有以下两种情况：

1. 用了若干张 $a_i$，此时前继状态为 $f_{i,j-a_i}$,由此转移即可。

2. 没有用一张 $a_i$，直接 $f_{i-1,j}$ 转移即可。

注意：需要初始化边界条件 $f_{i,0} \gets 1$。

贴出代码为：

for(int i = 1; i<=n; i++) {
	for(int j = 0; j <= w; j++) {
		if(j < a[i]) {
			f[i][j] = f[i-1][j];
		}
		else {
			f[i][j] = f[i][j-a[i]] + f[i-1][j];
			f[i][j] %= mod;
		}
	}
}

时间复杂度为 $O(nw)$，空间复杂度为 $O(nw)$，足以通过此题。

但是空间还可以再做优化，观察到 $f$ 的第一维 $i$ 只与 $i-1$ 有关，这样的转移是不必要的，直接去掉即可。

完整代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 1e3 + 5;
const int W = 1e4 + 5;
const int inf = 2e9;
const int mod = 1e9 + 7;
int n,w;
int a[N];
int f[W];

int main() {
	cin>>n>>w;
	for(int i = 1; i<=n; i++) {
		cin>>a[i];
	}
	f[0] = 1; //边界
	for(int i = 1; i<=n;i++) {
		for(int j = a[i]; j<=w; j++) {
			f[j] += f[j - a[i]] % mod;
			f[j] %= mod;
		}
	}
	cout<<f[w]<<endl;
	return 0;
}