PP4905 买表（提高）

解题思路

第一步，识别问题。 每种钱币有面额 v_i 和张数 s_i，要判断能否恰好凑出每块手表的价格。这是"多重背包可行性"问题：每个物品有数量限制，只问"能不能凑到"，不问最大价值。

第二步，设计状态。 用 dp[j] 表示"能否凑出 j 元"。dp[0]=true，其余为 false。最后只需要回答每个价格 q[i] 对应的 dp[q[i]] 是 true 还是 false。

第三步，按余数分组扫描。 对于面额为 v、张数为 s 的钱币，把金额按除以 v 的余数 r 分成几组。每一组里从小到大走，用一个计数器 cnt 记录"从最近一个能凑到的金额出发，还能再用几张这种钱币"。遇到能凑到的金额就把 cnt 重置为 s；否则如果 cnt 还大于 0，就说明可以用一张当前钱币接下去凑到，把 dp 标成 true 并让 cnt 减一。

第四步，回答询问。 处理完所有钱币后，对每块手表价格直接输出 Yes 或 No。

边界情况。 价格为 0 的手表一定能买（dp[0]=true）。面额大于最大价格的就不用处理了。

参考代码

// P4905 买表 多重背包：每种钱币张数有限，判断能否凑出价格
#include <iostream>
using namespace std;
int v[205], s[205]; // v 面额, s 张数
int q[100005]; // 手表价格
bool dp[500005]; // dp[j] 能否凑出 j 元
int main() {
    int n, m, i, cap = 0;
    cin >> n >> m;
    for (i = 0; i < n; i++) cin >> v[i] >> s[i];
    for (i = 0; i < m; i++) { cin >> q[i]; if (q[i] > cap) cap = q[i]; }
    dp[0] = true; // 0 元一定凑得出
    for (i = 0; i < n; i++) {
        if (v[i] > cap) continue; // 面额太大用不上
        // 按余数 r 分组扫描，cnt 记录还能用几张当前钱币
        for (int r = 0; r < v[i]; r++) {
            int cnt = 0;
            for (int j = r; j <= cap; j += v[i]) {
                if (dp[j]) cnt = s[i]; // 能凑到 j，从这里重新开始
                else if (cnt > 0) { dp[j] = true; cnt--; } // 用一张接下去
            }
        }
    }
    for (i = 0; i < m; i++)
        cout << (dp[q[i]] ? "Yes" : "No") << endl;
    return 0;
}

复杂度分析

时间复杂度是 O(n×cap)，其中 n 是钱币种类数（≤200），cap 是手表最大价格（≤5×10^5）。空间复杂度 O(cap)。