题目分析

题目描述： Tony有一些不同面值的硬币（A₁, A₂, ..., Aₙ），每种面值的硬币有对应的数量（C₁, C₂, ..., Cₙ）。他想买一块手表，手表的价格不超过m元。他希望恰好支付手表的价格（即不需要找零），但不知道手表的具体价格。我们需要计算在1到m范围内，Tony能恰好支付的价格有多少种。

输入格式：

• 每组测试用例的第一行是n（硬币种类数）和m（价格上限）。
• 第二行是2n个整数，前n个是硬币面值A₁, A₂, ..., Aₙ，后n个是硬币数量C₁, C₂, ..., Cₙ。
• 输入以0 0结束。

输出格式：

• 对于每组测试用例，输出1到m范围内Tony能恰好支付的价格数量。

示例输入：

3 10
1 2 4 2 1 1
2 5
1 4 2 1
0 0

示例输出：

8
4

解题思路

本题属于多重背包问题的变种，我们需要判断在给定的硬币面值和数量的情况下，1到m之间的哪些价格可以被恰好凑出。

方法：动态规划（DP）

1. 状态定义：

   • dp[j] 表示是否能凑出金额j（dp[j] >= 0表示可以，-1表示不行）。
   • 初始时，dp[0] = 0（金额0总是可以凑出），其余dp[j] = -1。

2. 状态转移：

   • 对于每种硬币面值A[i]，遍历金额j从0到m：
     • 如果dp[j] >= 0，说明当前金额j已经被凑出，可以继续使用剩余的硬币。
     • 如果j - A[i] >= 0且dp[j - A[i]] > 0，说明可以用A[i]来凑出j，并减少剩余硬币数量。

3. 最终答案：

   • 统计dp[1..m]中非负的个数，即为能凑出的价格数量。

标准程序（C++98）

#include <cstdio>
#include <cstring>

const int MAX_M = 100010;

int dp[MAX_M];
int A[101], C[101];

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) == 2 && (n || m)) {
        for (int i = 0; i < n; i++) scanf("%d", &A[i]);
        for (int i = 0; i < n; i++) scanf("%d", &C[i]);

        memset(dp, -1, sizeof(dp));
        dp[0] = 0; // 初始状态：金额0可以凑出

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= m; j++) {
                if (dp[j] >= 0) {
                    dp[j] = C[i]; // 如果j已经被凑出，剩余硬币数=C[i]
                } else if (j >= A[i] && dp[j - A[i]] > 0) {
                    dp[j] = dp[j - A[i]] - 1; // 使用1枚A[i]，剩余硬币数减1
                }
            }
        }

        int res = 0;
        for (int j = 1; j <= m; j++) {
            if (dp[j] >= 0) res++;
        }
        printf("%d\n", res);
    }
    return 0;
}

总结

• 题目类型：多重背包问题（是否能恰好凑出某个金额）。
• 关键点：
  • 动态规划状态设计（dp[j]表示剩余硬币数）。
  • 优化空间复杂度（使用一维数组）。
• 测试数据：
  • 包含小数据、大数据、边界情况（如所有硬币都能凑出所有金额）。
  • 确保程序能正确处理各种情况。

该解法时间复杂度为 O(n×m)，适用于题目给定的约束条件（n ≤ 100，m ≤ 100000）。