自动搬运

查看原文

来自洛谷，原作者为

	IntrepidStrayer The past is never dead. It's not even past.

搬运于2025-08-24 22:18:31，当前版本为作者最后更新于2020-03-12 17:04:50，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意：

有$K$种物品，价格分别为$1,2,...,K$。每种物品可以买无限次。用$n$元钱买物品，求刚好花完的方案数。

题解：

算法：完全背包

设$f_j$为刚好花完$j$元的方案数。刚好花完$j$元，可以看做刚好花完$j-i(1\le i\le j)$元，然后买了一个价格为$i$的物品。于是可以推出状态转移方程：

$f_j=\sum\limits_{i=1}^j f_{j-i}$

其中$f_0=1$，即不花钱有一种方案。

此题的答案超出了$long long$的范围，所以要用$\_\_int128$；而$\operatorname{printf}$不支持$\_\_int128$，所以要手写快写。

代码：

#include <cstdio>
#include <cstring>
using namespace std;
#define rei register int
#define FOR(i, l, r) for(rei i = l; i <= r; ++i)
typedef __int128 ll;
ll f[1001];
int n, m;
int print(ll x) {//快写
	if(x == 0) return putchar(48) + putchar(10);
	if(x >= 10) print(x / 10);
	putchar(x % 10 + 48);
}
signed main() {
	scanf("%d%d", &m, &n);
	f[0] = 1;
	FOR(i, 1, n)//外层循环枚举物品，内层循环枚举钱数，保证f[j-i]用到时已经计算过
		FOR(j, i, m)
			f[j] += f[j - i];
	print(f[m]);
	putchar(10);//换行
	return 0;
}