usaco-2.3.4 货币系统

题目描述

给定 $V$ 种货币面值（ $1 \leqslant V \leqslant 25$ ）和目标金额 $N$ （ $1 \leqslant N \leqslant 10{,}000$ ），求用这些面值恰好凑出 $N$ 的方案数，按组合计数：8x2+2x1 与 2x1+8x2 算同一种，答案保证在 long long 范围内。输入第 1 行是两个整数 $V$ 和 $N$ ，接下来 $V$ 行每行一个面值；输出单独一行方案数。

text

1
23 10
1 2 5

样例输出为 10。

思路

完全背包计数：设 ways[j] 为凑出金额 $j$ 的方案数，ways[0] = 1，外层枚举每种面值 $c$ 、内层金额 $j$ 正序执行 ways[j] += ways[j-c]。外层按面值分组保证同一方案的货币顺序不重复计数（组合而非排列），正序使 ways[j-c] 已含本轮值、同一面值可重复选。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 04:15
# update_at: 2026-10-01 04:15

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    v, n = next(data), next(data)
    coins = [next(data) for _ in range(v)]  # v 个面值，每行一个（token 化后与排版无关）

    # 完全背包计数：外层枚举面值，保证"按面值分组"，同一面值只能被重复选用，
    # 不同面值的使用顺序不产生新方案（即有序和 → 无序组合）。
    ways = [0] * (n + 1)
    ways[0] = 1  # 金额 0：不取任何货币，恰好一种方案
    for coin in coins:
        for amount in range(coin, n + 1):
            ways[amount] += ways[amount - coin]

    print(ways[n])


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 09:59
 * update_at: 2026-10-06 09:59
 */

#include <cstdio>

typedef long long ll;

const int MAXN = 10005; // 金额上限 10000

int v, n; // v 种面值，目标金额 n
int coin[30]; // coin[i] 第 i 种货币的面值
ll ways[MAXN]; // ways[j] 表示用已处理过的面值凑出金额 j 的方案数

int main() {
    scanf("%d %d", &v, &n);
    for (int i = 1; i <= v; ++i)
        scanf("%d", &coin[i]);

    // 完全背包计数：外层按面值分组，保证同一种方案的货币顺序不重复计数
    ways[0] = 1; // 金额 0：什么都不取，恰好一种方案
    for (int i = 1; i <= v; ++i)
        for (int j = coin[i]; j <= n; ++j) // 金额正序：ways[j-c] 已含本轮值，同一面值可重复选
            ways[j] += ways[j - coin[i]];

    printf("%lld\n", ways[n]);
    return 0;
}

usaco-2.3.4 货币系统

目录

题目描述

思路

参考代码