[USACO3.3] 商店购物 Shopping Offers

题意

商店里有若干种优惠包，每个优惠包会把若干件商品打包出售。

最后顾客只关心 b 种商品，每种商品给出：

商品编号
需要购买的件数
单买价格

要求恰好买到这些商品，不能多买，并让总花费最小。

思路

先看一个可以直接验证想法的朴素解：

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#include <bits/stdc++.h>
using namespace std;

const int MAXS = 110;
const int MAXB = 5;
const int MAXO = 120;
const int MAXSTATE = 8000;
const int INF = 1e9;

struct RawOffer {
    int item_cnt;
    int code[6];
    int num[6];
    int price;
} raw_offer[MAXS];

struct Offer {
    int num[MAXB];
    int price;
} offer[MAXO];

int s, b;
int target_code[MAXB], need[MAXB], single_price[MAXB];
int pow6[6];
int offer_cnt;
int memo[MAXSTATE];
bool vis[MAXSTATE];

int get_id(int code) {
    for (int i = 0; i < b; i++) {
        if (target_code[i] == code) {
            return i;
        }
    }
    return -1;
}

void add_offer(int cnt[], int price) {
    offer_cnt++;
    for (int i = 0; i < b; i++) {
        offer[offer_cnt].num[i] = cnt[i];
    }
    offer[offer_cnt].price = price;
}

int dfs(int state) {
    if (state == 0) {
        return 0;
    }
    if (vis[state]) {
        return memo[state];
    }
    vis[state] = true;

    int rem[MAXB] = {0};
    int x = state;
    for (int i = 0; i < b; i++) {
        rem[i] = x % 6;
        x /= 6;
    }

    int ans = INF;

    for (int k = 1; k <= offer_cnt; k++) {
        bool ok = true;
        int next_state = state;

        for (int i = 0; i < b; i++) {
            if (offer[k].num[i] > rem[i]) {
                ok = false;
                break;
            }
            next_state -= offer[k].num[i] * pow6[i];
        }

        if (ok) {
            ans = min(ans, dfs(next_state) + offer[k].price);
        }
    }

    memo[state] = ans;
    return ans;
}

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

    // brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
    // 从目标购买状态出发，递归尝试最后一次使用哪一个优惠包或单买方案。
    cin >> s;
    for (int i = 1; i <= s; i++) {
        cin >> raw_offer[i].item_cnt;
        for (int j = 0; j < raw_offer[i].item_cnt; j++) {
            cin >> raw_offer[i].code[j] >> raw_offer[i].num[j];
        }
        cin >> raw_offer[i].price;
    }

    cin >> b;
    for (int i = 0; i < b; i++) {
        cin >> target_code[i] >> need[i] >> single_price[i];
    }

    for (int i = 1; i <= s; i++) {
        int cnt[MAXB] = {0};
        bool bad = false;
        bool useful = false;

        for (int j = 0; j < raw_offer[i].item_cnt; j++) {
            int id = get_id(raw_offer[i].code[j]);
            if (id == -1) {
                bad = true;
                break;
            }
            cnt[id] += raw_offer[i].num[j];
            useful = true;
        }

        if (!bad && useful) {
            add_offer(cnt, raw_offer[i].price);
        }
    }

    for (int i = 0; i < b; i++) {
        int cnt[MAXB] = {0};
        cnt[i] = 1;
        add_offer(cnt, single_price[i]);
    }

    pow6[0] = 1;
    for (int i = 1; i <= b; i++) {
        pow6[i] = pow6[i - 1] * 6;
    }

    int target_state = 0;
    for (int i = 0; i < b; i++) {
        target_state += need[i] * pow6[i];
    }

    cout << dfs(target_state) << '\n';
    return 0;
}

因为最多只会买 5 种商品，而且每种需要的数量也不大，所以最自然的状态就是：

(c1, c2, c3, c4, c5)

表示当前已经买了多少件。

为了让程序更好写，可以把它编码成一个 6 进制数：

state = c1 + c2 * 6 + c3 * 6^2 + ...

这样每个状态都唯一对应一种购买情况。

接下来把所有“可用的购买方式”统一起来：

题目给出的优惠包
每种商品单独买 1 件

于是每个优惠包都可以看成一次状态转移：

它让某几种商品的购买数增加
总花费增加这个优惠包的价格

正式做法是正向 DP：

dp[state] = 买到 state 这个状态所需的最小花费

从全 0 状态开始，枚举每个优惠包，尝试转移到下一个状态。
如果某个优惠包会让某种商品买超了，就不能使用。

最终目标状态就是“每种商品都刚好买够”的那个编码值。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXS = 110;
const int MAXB = 5;
const int MAXO = 120;
const int MAXSTATE = 8000;
const int INF = 1e9;

struct RawOffer {
    int item_cnt;
    int code[6];
    int num[6];
    int price;
} raw_offer[MAXS];

struct Offer {
    int num[MAXB];
    int price;
} offer[MAXO];

int s, b;
int target_code[MAXB], need[MAXB], single_price[MAXB];
int pow6[6];
int offer_cnt;
int dp[MAXSTATE];

int get_id(int code) {
    for (int i = 0; i < b; i++) {
        if (target_code[i] == code) {
            return i;
        }
    }
    return -1;
}

void add_offer(int cnt[], int price) {
    offer_cnt++;
    for (int i = 0; i < b; i++) {
        offer[offer_cnt].num[i] = cnt[i];
    }
    offer[offer_cnt].price = price;
}

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

    cin >> s;
    for (int i = 1; i <= s; i++) {
        cin >> raw_offer[i].item_cnt;
        for (int j = 0; j < raw_offer[i].item_cnt; j++) {
            cin >> raw_offer[i].code[j] >> raw_offer[i].num[j];
        }
        cin >> raw_offer[i].price;
    }

    cin >> b;
    for (int i = 0; i < b; i++) {
        cin >> target_code[i] >> need[i] >> single_price[i];
    }

    for (int i = 1; i <= s; i++) {
        int cnt[MAXB] = {0};
        bool bad = false;
        bool useful = false;

        for (int j = 0; j < raw_offer[i].item_cnt; j++) {
            int id = get_id(raw_offer[i].code[j]);
            if (id == -1) {
                bad = true;
                break;
            }
            cnt[id] += raw_offer[i].num[j];
            useful = true;
        }

        if (!bad && useful) {
            add_offer(cnt, raw_offer[i].price);
        }
    }

    // 把原价单买也当成普通优惠包，这样状态转移就统一了。
    for (int i = 0; i < b; i++) {
        int cnt[MAXB] = {0};
        cnt[i] = 1;
        add_offer(cnt, single_price[i]);
    }

    pow6[0] = 1;
    for (int i = 1; i <= b; i++) {
        pow6[i] = pow6[i - 1] * 6;
    }

    int total_state = pow6[b];
    int target_state = 0;
    for (int i = 0; i < b; i++) {
        target_state += need[i] * pow6[i];
    }

    for (int i = 0; i < total_state; i++) {
        dp[i] = INF;
    }
    dp[0] = 0;

    for (int state = 0; state < total_state; state++) {
        if (dp[state] == INF) {
            continue;
        }

        int cur[MAXB] = {0};
        int x = state;
        bool valid = true;
        for (int i = 0; i < b; i++) {
            cur[i] = x % 6;
            x /= 6;
            if (cur[i] > need[i]) {
                valid = false;
                break;
            }
        }
        if (!valid) {
            continue;
        }

        for (int k = 1; k <= offer_cnt; k++) {
            int next_state = state;
            bool ok = true;

            for (int i = 0; i < b; i++) {
                if (cur[i] + offer[k].num[i] > need[i]) {
                    ok = false;
                    break;
                }
                next_state += offer[k].num[i] * pow6[i];
            }

            if (ok) {
                dp[next_state] = min(dp[next_state], dp[state] + offer[k].price);
            }
        }
    }

    cout << dp[target_state] << '\n';
    return 0;
}

复杂度

因为最多只有 5 种商品，每种数量按 0..5 处理，状态总数最多是：

6^5 = 7776

设可用优惠包总数为 m，则：

时间复杂度 $O(6^5 * m * 5)$
空间复杂度 $O(6^5)$

总结

这题的关键不是优惠怎么选，而是先把“购买数量”变成小状态。

一旦把每种商品当前已买数量看成状态，题目就变成非常标准的“小状态最小花费 DP”。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

[USACO3.3] 商店购物 Shopping Offers

目录

题意

思路

代码

复杂度

总结

一图流解析