usaco-3.3.2 商店购物

形式化题目

给定若干种优惠套餐，每个套餐是一组商品的数量组合加上一个总价；再给定一张购物清单，列出要买的商品种类、每种的数量和它的原价。

购买时可以对同一套餐使用任意多次，也可以用原价单独购买任意一件商品。要求恰好买齐清单上的每一种商品，不允许顺带多买清单之外的商品，也不允许为了凑优惠而多买清单内的商品。

求买齐清单所需的最小总花费。

形式化地，设清单共有 $b \leqslant 5$ 种商品，第 $i$ 种要买 $w_i \leqslant 5$ 件、单价为 $p_i$ ；第 $j$ 个优惠套餐在清单各维度上的份数向量为 $v^{(j)} \in \mathbb{Z}_{\geqslant 0}^{b}$ ，价格为 $q_j$ 。求

\min \sum_j x_j q_j + \sum_i r_i p_i \quad\text{s.t.}\quad \sum_j x_j v^{(j)} + r = w,\quad x_j \in \mathbb{Z}_{\geqslant 0},\ r_i \geqslant 0 .

正解

思路

朴素的枚举。 最直接的想法是从需求向量 $w$ 出发做深度优先搜索：每一步挑一个"此刻还装得下"的优惠套餐扣掉它，扣不动了就把剩下的商品全部按原价补齐，用总花费更新答案。

这个搜索是正确的，但会爆炸。优惠套餐最多 $99$ 个，总件数最多 $5 \times 5 = 25$ 件，分支因子按 $s + b$ 估算，量级达到 $(s+b)^{25}$ ，完全跑不动。

瓶颈在哪里。 真正的问题不是"方案多"，而是同一个剩余需求被反复求解。用样例来说，清单要买 3 朵花、2 个花瓶，下面两条完全不同的搜索路径会到达同一个剩余向量 $(0,2)$ ：

按原价买 3 次花，单价 2z，共花 6z；
套一次"3 朵花 = 5z"的套餐，花 5z。

到达 $(0,2)$ 之后，"还差 2 个花瓶"这件事的后续最优代价完全一样，但朴素 DFS 会把它重算一遍。更一般地，剩余向量 $(r_1, \dots, r_b)$ 本身就是完备的信息——它精确描述了还差什么、还差多少，与"之前是怎么扣的、花了多少钱"完全无关。所以问题的真实规模不是方案组合数，而是状态个数。

状态有多大。 清单最多 5 种商品，每种最多买 5 件，所以每个维度取值范围是 $0 \sim 5$ ，状态总数不超过

(5+1)^{5} = 6^{5} = 7776 .

把 $99^{25}$ 量级的搜索压到 7776 个状态，这就是本题的全部关键。

转移的两条边。 把问题看成一张状态图，节点是剩余需求向量 left，从 left 出发有两种边：

原价边：把某一维减 1，代价是该商品单价 $p_i$ 。
套餐边：如果 left - v^{(j)} 每一维都非负，就走到那个状态，代价是套餐价 $q_j$ 。这个非负条件正是题面"不能多买"的直接翻译。

因为每个套餐在每一维上的份数都不超过该商品的总需求（两者都受 5 的约束），所以同一个套餐无论重复几次，都会被"某一维扣成负数"挡住——用完即止，天然有界，不需要额外记录"某套餐用了几次"的维度，状态依然只有 $b$ 维。这一点很重要：如果套餐份数可以超过总需求，状态就必须再乘上一个"各套餐剩余可用次数"的维度，空间会爆炸。

为什么不会死循环。 两类转移都把 $\sum_i left_i$ 严格减小（原价边减 1，非空套餐边至少减 1），状态有限，所以状态图是 DAG，记忆化递归必然终止。前提是丢掉"所有分量都为 0"的空套餐——那种套餐等于白送，会形成零代价自环。

于是得到值函数

\mathrm{best}(left) = \min\Bigl(\min_{i:\,left_i>0}\bigl(p_i + \mathrm{best}(left - e_i)\bigr),\ \min_{j:\,left - v^{(j)} \geqslant 0}\bigl(q_j + \mathrm{best}(left - v^{(j)})\bigr)\Bigr),

边界 $\mathrm{best}(0) = 0$ ，答案就是 $\mathrm{best}(w)$ 。原价边保证任何状态都有后继，所以永远有解，不会出现"卡住"。

以样例验证。 样例清单是 3 朵花（单价 2z）和 2 个花瓶（单价 5z），套餐有"3 朵花 5z"和"2 花瓶 + 1 花 10z"。下表列出两维状态网格中每个 $(\text{剩余花}, \text{剩余花瓶})$ 的最优值，行是剩余花数，列是剩余花瓶数，单元格里的数字是 $\mathrm{best}(left)$ ：

$\mathrm{best}$	花瓶 0	花瓶 1	花瓶 2
花 0	0	5	10
花 1	2	7	10
花 2	4	9	12
花 3	5	10	14

读者可以重点观察三个格子。 $(0,2) = 10$ ：只剩两个花瓶，而"1 花 + 2 花瓶"套餐要求恰好 1 朵花，此刻花已经为 0，套餐用不上，只能按原价买两个花瓶， $2 \times 5 = 10$ 。 $(1,2) = 10$ ：这里恰好够套一次"1 花 + 2 花瓶 = 10z"的套餐，一次性清零，比按原价 $2 + 10 = 12$ 省 2z——可见优惠只在"剩余需求刚好被套餐覆盖"时才发挥作用。右下角 $(3,2) = 14$ ：全按原价要 $3 \times 2 + 2 \times 5 = 16$ z，套一次套餐（10z）后只剩 2 朵花按原价 4z，合计 14z，正是样例答案。

注意 $(3,2)$ 的 14 也说明**"按原价补齐"本身就是一种合法的边**：套完一次套餐后剩下的 2 朵花既可以直接买，也可能再被别的套餐覆盖，DP 会自动在所有后继里取最小，不需要人为规定"先尽量用套餐"的贪心顺序。

实现细节。 优惠套餐里可能出现购物清单之外的商品，比如清单只有编号 7，套餐却是"1 件 7 号 + 2 件 8 号"。这样的套餐一旦使用就必然多买 8 号，与题面矛盾，必须在预处理阶段丢弃：把套餐的编号对逐一代入清单映射，任何一个编号不在映射里就整条丢弃。剩下的套餐写成维度向量；若两条套餐扣的向量相同，只保留便宜的那条。

状态用元组表示，元组可哈希，正好可以直接当 functools.cache 的键，省掉手工进制编码。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 05:22
# update_at: 2026-10-01 05:22

import sys
from functools import cache


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))

    # offer = ((单品下标, 份数), ...) + 优惠价；只保留被购物清单覆盖的方案，
    # 这样状态向量的每一维都恰好对应一种要买的商品。
    raw: list[tuple[list[tuple[int, int]], int]] = []
    for _ in range(next(data)):
        n = next(data)
        pairs = [(next(data), next(data)) for _ in range(n)]  # 必须立即求值，否则 p 会先被读走
        raw.append((pairs, next(data)))

    count_of_species = next(data)
    order = [next(data) for _ in range(count_of_species * 3)]
    # 清单按商品编号排序，方便下面把优惠方案里的编号换算成状态维度下标。
    species = sorted((order[i * 3], order[i * 3 + 1], order[i * 3 + 2]) for i in range(count_of_species))
    index_of = {c: i for i, (c, _, _) in enumerate(species)}
    want = tuple(k for _, k, _ in species)

    # 每个方案表示成 len(species) 长的份数向量 + 价格；同一个向量可能有多个报价，取最小。
    deals: dict[tuple[int, ...], int] = {}
    for pairs, price in raw:
        need = [0] * count_of_species
        for c, k in pairs:
            if c not in index_of:  # 方案里出现清单外的商品：题面禁止顺带购买，丢弃
                break
            need[index_of[c]] = k
        else:
            key = tuple(need)
            if key != tuple([0] * count_of_species):  # 空方案等于白送，不合题意
                deals[key] = min(deals.get(key, price), price)
    options = [(key, price) for key, price in deals.items()]

    @cache
    def best(left: tuple[int, ...]) -> int:
        """left 为各商品还差几件时的最低花费：要么按原价买一件，要么用某个能装下的方案。"""
        if not any(left):
            return 0
        ans = 10**9
        for i, rest in enumerate(left):
            if rest:  # 按原价补一件，保证状态一定向 0 收敛
                ans = min(ans, species[i][2] + best(left[:i] + (rest - 1,) + left[i + 1:]))
        for key, price in options:
            nxt = tuple(a - b for a, b in zip(left, key))
            if min(nxt) >= 0:  # 方案不超过剩余需求，题面禁止多买
                ans = min(ans, price + best(nxt))
        return ans

    print(best(want))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 09:59
 * update_at: 2026-10-06 09:59
 */
#include <algorithm>
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXS = 100;   // 优惠套餐数上限
const int MAXDIM = 5;   // 清单商品种类数上限
const int STATE = 7776; // 6^5：每种商品最多买 5 件，状态编码上界

struct Species {
    ll id;    // 商品编号
    ll num;   // 需要购买的件数
    ll price; // 原价
};

ll species_cnt;
Species species[MAXDIM]; // 购物清单，排序后第 i 项对应状态的第 i 维

int index_of[1000]; // index_of[商品编号] = 维度下标，不在清单中则为 -1

ll raw_cnt[MAXS];            // 第 t 个套餐包含的商品种类数
ll raw_id[MAXS][MAXDIM];     // 第 t 个套餐的第 i 种商品编号
ll raw_num[MAXS][MAXDIM];    // 第 t 个套餐的第 i 种商品份数
ll raw_price[MAXS];          // 第 t 个套餐的优惠价

ll deal_code[MAXS];          // 保留的套餐编码成 6 进制数
ll deal_digit[MAXS][MAXDIM]; // 保留的套餐在各维上的份数
ll deal_price[MAXS];         // 保留的套餐的优惠价
ll deal_cnt;                 // 去重后保留的套餐数

ll best_price[STATE]; // best_price[code] 存同一份数向量的最低套餐价，-1 表示无
ll memo[STATE];       // memo[code] = 剩余需求为 code 时的最低花费，-1 表示未算过
ll pow6[MAXDIM + 1];  // pow6[i] = 6^i，用于状态与向量的进位编码

// 按商品编号升序排列，使清单维度与编号顺序对应，便于把套餐换算成维度向量。
bool cmp_species(Species a, Species b) {
    return a.id < b.id;
}

// 把一份剩余需求向量编码成 6 进制整数。
ll encode(ll left[]) {
    ll code = 0;
    for (ll i = 0; i < species_cnt; i++) {
        code = code + left[i] * pow6[i];
    }
    return code;
}

// 读取套餐与购物清单，并把套餐换算成清单维度上的份数向量。
void read_input() {
    ll s;
    cin >> s;
    for (ll t = 0; t < s; t++) {
        cin >> raw_cnt[t];
        for (ll i = 0; i < raw_cnt[t]; i++) {
            cin >> raw_id[t][i] >> raw_num[t][i];
        }
        cin >> raw_price[t];
    }

    cin >> species_cnt;
    for (ll i = 0; i < species_cnt; i++) {
        cin >> species[i].id >> species[i].num >> species[i].price;
    }
    sort(species, species + species_cnt, cmp_species);
    for (ll i = 0; i < 1000; i++) {
        index_of[i] = -1;
    }
    for (ll i = 0; i < species_cnt; i++) {
        index_of[species[i].id] = (int)i;
    }

    pow6[0] = 1;
    for (ll i = 1; i <= MAXDIM; i++) {
        pow6[i] = pow6[i - 1] * 6;
    }
    for (ll i = 0; i < STATE; i++) {
        best_price[i] = -1;
        memo[i] = -1;
    }

    for (ll t = 0; t < s; t++) {
        ll digit[MAXDIM];
        for (ll i = 0; i < MAXDIM; i++) {
            digit[i] = 0;
        }
        bool valid = true;
        for (ll i = 0; i < raw_cnt[t]; i++) {
            int pos = index_of[raw_id[t][i]];
            if (pos == -1) { // 套餐含清单外商品，题面禁止顺带购买，整条丢弃
                valid = false;
                break;
            }
            digit[pos] = raw_num[t][i];
        }
        if (!valid) {
            continue;
        }
        bool empty = true;
        for (ll i = 0; i < species_cnt; i++) {
            if (digit[i] > 0) {
                empty = false;
            }
        }
        if (empty) { // 空套餐等于白送，会形成零代价自环，丢弃
            continue;
        }
        ll code = encode(digit);
        if (best_price[code] == -1 || raw_price[t] < best_price[code]) {
            best_price[code] = raw_price[t];
        }
    }

    for (ll code = 0; code < STATE; code++) {
        if (best_price[code] != -1) {
            deal_code[deal_cnt] = code;
            deal_price[deal_cnt] = best_price[code];
            ll rest = code;
            for (ll i = 0; i < species_cnt; i++) {
                deal_digit[deal_cnt][i] = rest % 6;
                rest = rest / 6;
            }
            deal_cnt++;
        }
    }
}

// 记忆化搜索：left 为各商品还差几件时的最低花费。
// 每次要么按原价买一件，要么套用一个不超过剩余需求的套餐。
ll dfs(ll code) {
    if (code == 0) {
        return 0;
    }
    if (memo[code] != -1) {
        return memo[code];
    }
    ll left[MAXDIM];
    ll rest = code;
    for (ll i = 0; i < species_cnt; i++) {
        left[i] = rest % 6;
        rest = rest / 6;
    }

    ll ans = -1;
    for (ll i = 0; i < species_cnt; i++) {
        if (left[i] > 0) { // 按原价补一件，保证状态一定向 0 收敛
            ll cand = species[i].price + dfs(code - pow6[i]);
            if (ans == -1 || cand < ans) {
                ans = cand;
            }
        }
    }
    for (ll j = 0; j < deal_cnt; j++) {
        bool fit = true;
        for (ll i = 0; i < species_cnt; i++) {
            if (left[i] < deal_digit[j][i]) { // 套餐超过剩余需求，题面禁止多买
                fit = false;
                break;
            }
        }
        if (!fit) {
            continue;
        }
        ll cand = deal_price[j] + dfs(code - deal_code[j]);
        if (ans == -1 || cand < ans) {
            ans = cand;
        }
    }

    memo[code] = ans;
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    read_input();

    ll want[MAXDIM];
    for (ll i = 0; i < species_cnt; i++) {
        want[i] = species[i].num;
    }
    cout << dfs(encode(want)) << endl;

    return 0;
}

复杂度

设清单种类数 $b \leqslant 5$ 、每种件数 $w_i \leqslant 5$ 、套餐数 $s \leqslant 99$ 。

状态数 $N = \prod_i (w_i + 1) \leqslant 6^5 = 7776$ ，每个状态转移一次不再重算。
每个状态枚举 $b$ 条原价边与至多 $s$ 条套餐边，每条转移构造向量需要 $O(b)$ 。
时间 $O\bigl(N \cdot (b + s) \cdot b\bigr)$ ，最坏约 $4 \times 10^6$ 次基本操作；空间 $O(N + sb)$ ，递归深度不超过 $25$ 。

与标准的多维背包正解同阶。

总结

这道题的突破口是认清剩余需求向量 $\left(r_1, \dots, r_b\right)$ 就是完备状态：它只关心"还差什么"，不关心"之前按什么顺序扣的"。一旦接受这一点， $(s+b)^{25}$ 的枚举就塌缩成 $6^5 = 7776$ 个互不重复的子问题，记忆化搜索直接解决。

三个容易写错的地方：一是套餐含清单外商品必须整条丢弃，二是空套餐要排除以免形成零代价自环，三是"不能多买"要落成 left - v 各维非负的判定。原价边既是保底（保证有解），也是保证状态图无环的收敛边。

usaco-3.3.2 商店购物

目录

形式化题目

正解

思路

代码

复杂度

总结