题解 P6205 【[USACO06JAN]Dollar Dayz S】

· · 题解

题意：

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