1 条题解
-
0
【本题解由站长编写】
最多 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
- 上传者