跳至正文

1 条题解

  • 0
    @ 2026-10-8 18:18:52

    【本题解由站长编写】

    最多 5 种商品、每种最多 5 件,把「各种商品还差多少件」用 6 进制编码成一个状态(每位 0..5),最多 6^5 = 7776 个状态。记忆化 solve(state) 返回补齐剩余需求的最少花费:

    • 终止:所有剩余需求为 0,返回 0。
    • 兜底:剩余全按原价买齐,永远合法,用它初始化上界。
    • 转移:枚举每个促销方案,把它提供的数量从剩余需求里扣掉、加上方案价,递归取最小;若某项超过剩余需求就跳过(题目禁止买多)。

    ⚠️ 输入格式的坑(最容易错的地方):题面写「第一个整数 n(1<=n<=5),表示这种优惠方式由 n 种商品组成。后面 n 对整数 c 和 k」。但实际数据是 n c₁ k₁ c₂ k₂ … cₙ kₙ p——n 是种类数,后面跟 n 组「编号 + 件数」,最后才是价格 p,不是「n 组 (c,k) 之后再跟一个 n」。按后者解析,样例 3 的 1 641 1 46 会被读成「1 组 (641,1),价格 46」而不是「1 种商品 641 共 1 件、46 元」——实际上巧合地只差在把 46 当成了价格,看起来一样;但 1 262 2 200 若按错格式读成「1 组 (262,2) 价格 200」就完全错了,因为它本该是「1 种商品 262 共 2 件、200 元」。样例 3 真实含义是:商品 641×1 售 46、262×2 售 200、83×3 售 55、24×1 与 105×2 售 205。

    另外两点:同一份方案可重复购买(样例 3 限买 1 次得 1631、限买 5 次才命中 1563),记忆化天然覆盖;方案里含清单外商品时只取落在清单内的那部分,不整份丢弃。

    代码(C++17)

    #include <bits/stdc++.h>
    using namespace std;
    
    int pw6[6];
    int need[5], price[5], have;
    struct Plan { vector<pair<int, int>> items; int price; };
    vector<Plan> plans;
    int memo[7776];
    
    int solve(int state) {
        int &res = memo[state];
        if (res != -1) return res;
    
        int rem[5], t = state;
        bool allZero = true;
        for (int i = 0; i < have; i++) {
            rem[i] = t % 6; t /= 6;
            if (rem[i]) allZero = false;
        }
        if (allZero) return res = 0;
    
        res = 0;
        for (int i = 0; i < have; i++) res += rem[i] * price[i];
    
        for (const Plan &pl : plans) {
            int ns = state;
            bool ok = true;
            for (auto &it : pl.items) {
                if (rem[it.first] < it.second) { ok = false; break; }
                ns -= it.second * pw6[it.first];
            }
            if (!ok) continue;
            res = min(res, pl.price + solve(ns));
        }
        return res;
    }
    
    int main() {
        pw6[0] = 1;
        for (int i = 1; i <= 5; i++) pw6[i] = pw6[i - 1] * 6;
    
        int s;
        cin >> s;
        vector<Plan> raw;
        for (int i = 0; i < s; i++) {
            int n;
            cin >> n;                       // n = 商品种类数
            vector<pair<int, int>> items;
            for (int j = 0; j < n; j++) {
                int c, k;
                cin >> c >> k;               // n 组「编号 c、件数 k」
                items.push_back({c, k});
            }
            int p;
            cin >> p;                       // 最后才是价格
            raw.push_back({items, p});
        }
    
        int b;
        cin >> b;
        int slot[1000];
        fill(slot, slot + 1000, -1);
        have = 0;
        for (int i = 0; i < b; i++) {
            int c, k, pr;
            cin >> c >> k >> pr;
            if (slot[c] == -1) slot[c] = have++;
            need[slot[c]] = k;
            price[slot[c]] = pr;
        }
    
        // 方案里只保留落在清单内的商品(合并同编号),全不在清单内的丢弃
        for (auto &pl : raw) {
            int cnt[5] = {0};
            for (auto &it : pl.items) if (slot[it.first] != -1) cnt[slot[it.first]] += it.second;
            Plan np;
            np.price = pl.price;
            for (int i = 0; i < have; i++) if (cnt[i]) np.items.push_back({i, cnt[i]});
            if (!np.items.empty()) plans.push_back(np);
        }
    
        int start = 0;
        for (int i = 0; i < have; i++) start += need[i] * pw6[i];
    
        fill(memo, memo + 7776, -1);
        cout << solve(start) << endl;
        return 0;
    }
    
    • 1

    信息

    ID
    4149
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    3
    已通过
    0
    上传者