解题思路

本题等价于有限次硬币找零（组合数）：给出若干奖品价值（可有重复），每个出现的奖品只能使用一次；若某价值出现多次，则该价值可使用的数量等于其出现次数。我们要统计不计顺序、总价值恰为 num 的组合个数。

做法：

1. 先将 values 压缩为「价值 -> 频次」的映射，例如 4 出现 2 次表示面值 4 的“硬币”有 2 个。
2. 使用二维计数 DP（组合型）： 设 dp[s] 表示处理完若干种价值后，凑出和为 s 的组合数。对每一种价值 v（可用 cnt 次），转移：

初始 dp[0]=1（什么都不选）。依次按价值种类更新。 3. 由于 len, num ≤ 100，上述三重循环（价值种类 × 目标和 × 可选件数）复杂度可接受，且能正确避免排列重复（只按价值种类逐类选择）。

复杂度分析

• 时间复杂度：$O(M \times \text{num} \times K)$，其中 $M$ 为不同价值的种数，$K$ 约为 num / v 的均值；在本题数据范围内不超过约 $10^6$ 级别，完全可行。
• 空间复杂度：$O(\text{num}+1)$，使用两个一维数组滚动更新。

代码实现

Python

# 题面功能放在外部函数里，主函数只做输入输出
from collections import Counter
import sys

def count_combinations(values, num):
    # 压缩为 价值->频次
    freq = Counter(values)
    dp = [0] * (num + 1)
    dp[0] = 1  # 和为0的组合只有不选

    for v, cnt in freq.items():
        next_dp = [0] * (num + 1)
        for s in range(0, num + 1):
            # 选 k 个当前价值 v
            max_k = min(cnt, s // v) if v != 0 else 0
            total = 0
            # 累加 dp[s - k*v]
            for k in range(0, max_k + 1):
                total += dp[s - k * v]
            next_dp[s] = total
        dp = next_dp
    return dp[num]

def main():
    data = sys.stdin.read().strip().split()
    # 输入为：
    # len
    # values(len个)
    # num
    idx = 0
    n = int(data[idx]); idx += 1
    values = list(map(int, data[idx:idx+n])); idx += n
    num = int(data[idx])
    print(count_combinations(values, num))

if __name__ == "__main__":
    main()

Java

// 类名必须为 Main，ACM 风格
import java.util.*;
import java.io.*;

public class Main {

    // 题面功能：统计组合数
    static long countCombinations(int[] values, int num) {
        // 统计价值频次
        Map<Integer, Integer> freq = new HashMap<>();
        for (int v : values) {
            freq.put(v, freq.getOrDefault(v, 0) + 1);
        }

        long[] dp = new long[num + 1];
        dp[0] = 1;

        for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
            int v = e.getKey();
            int cnt = e.getValue();
            long[] next = new long[num + 1];
            for (int s = 0; s <= num; s++) {
                long total = 0;
                int maxK = (v == 0) ? 0 : Math.min(cnt, s / v);
                for (int k = 0; k <= maxK; k++) {
                    total += dp[s - k * v];
                }
                next[s] = total;
            }
            dp = next;
        }
        return dp[num];
    }

    public static void main(String[] args) throws Exception {
        // 默认用 Scanner，数据范围不大
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] values = new int[n];
        for (int i = 0; i < n; i++) values[i] = sc.nextInt();
        int num = sc.nextInt();
        System.out.println(countCombinations(values, num));
        sc.close();
    }
}

C++

// ACM 风格，主函数处理输入输出，功能放外部函数
#include <bits/stdc++.h>
using namespace std;

// 统计组合数（有限次、按价值计数）
long long countCombinations(const vector<int>& values, int num) {
    // 统计价值出现次数
    unordered_map<int, int> mp;
    mp.reserve(values.size() * 2);
    for (int v : values) mp[v]++;

    vector<long long> dp(num + 1, 0);
    dp[0] = 1;

    for (auto &it : mp) {
        int v = it.first;
        int cnt = it.second;
        vector<long long> next(num + 1, 0);
        for (int s = 0; s <= num; ++s) {
            long long total = 0;
            int maxK = (v == 0) ? 0 : min(cnt, s / v);
            for (int k = 0; k <= maxK; ++k) {
                total += dp[s - k * v];
            }
            next[s] = total;
        }
        dp.swap(next);
    }
    return dp[num];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; 
    if (!(cin >> n)) return 0;
    vector<int> values(n);
    for (int i = 0; i < n; ++i) cin >> values[i];
    int num; cin >> num;
    cout << countCombinations(values, num) << "\n";
    return 0;
}

题目内容

游乐场通过进行游戏获取游戏币，游戏币可以用来兑换奖品，每个品价值不同的游戏币数量。可兑换的奖品列表通过数组 $values$ 给出，其中 $values[i]$ 表示兑换第 $i$ 个奖品价值的游戏币数量，价值相同则记为同一奖品。给出获取的游戏币数量 $num$ ，请计算刚好价值 $num$ 个游戏币的奖品组合的个数，如果不存在价值 $num$ 个游戏币的奖品组合，则返回 $0$ 。

输入描述

第一行:正整数 $len$ ，表示奖品列表 $values$ 长度，$1<=len<=100$ ;

第二行:正整数数组 $values$ ，长度为 $len$ ，$values[i]$ 表示第 $i$ 个奖品价值的游戏币数量，$1 <=values[i]<=100$ ;

第三行:正整数 $num$ ，表示获取的游戏币数量，$0<=num<=100$ .

输出描述

整数，代表本次可以兑换的奖品组台数量

样例1

输入

3
3 3 3
4

输出

0

说明

无可以兑换的奖品组合，输出 $0$

样例2

输入

8
2 5 4 5 3 7 1 4
8

输出

5

说明

可以兑换的奖品组合为: $[$

$[2 ,5,1]$

$[5,3]$

$[4,4]$

$[4,3,1]$

$[7,1]$

$]$

输出组合数量 $5$