[ICPC 2014 WF] Buffed Buffet

GitHub 跳转原题关系图返回列表

离散菜先做凹费用完全背包求每个整数重量的最优值，连续菜再把剩余重量写成分段二次函数最优分配，最后合并两部分答案。

OJ: luogu

题目 ID: P6893

难度:提高+/省选-

标签:动态规划背包状态设计分类讨论

日期: 2026-06-21 10:15

题意

有两类菜：

离散菜：每份重量固定，只能取整数份
连续菜：可以取任意实数重量

第 i 道菜都有初始美味值 t_i 和衰减速度 Δt_i。

如果是一道离散菜，取第 n 份时的边际美味值是：

t_i - (n-1)Δt_i

如果是一道连续菜，已经取了 x 克后，再取一个无穷小 dx 的边际美味值是：

(t_i - xΔt_i)dx

要求总重量恰好为 W，并让总美味值最大。

思路

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

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

const long double NEG_INF = -1e100L;

struct DiscreteDish {
    int weight;
    long double t;
    long double d;
};

struct ContinuousDish {
    long double t;
    long double d;
};

int n, W;
vector<DiscreteDish> discrete_dishes;
vector<ContinuousDish> continuous_dishes;
vector<long double> cont_best;
long double answer;

void solve_continuous_part() {
    cont_best.assign(W + 1, NEG_INF);
    cont_best[0] = 0;

    if (continuous_dishes.empty()) {
        return;
    }

    long double best_const = NEG_INF;
    vector<ContinuousDish> quad;

    for (size_t i = 0; i < continuous_dishes.size(); i++) {
        if (fabsl(continuous_dishes[i].d) < 1e-18L) {
            best_const = max(best_const, continuous_dishes[i].t);
        } else {
            quad.push_back(continuous_dishes[i]);
        }
    }

    if (best_const > NEG_INF / 2) {
        vector<ContinuousDish> filtered;
        for (size_t i = 0; i < quad.size(); i++) {
            if (quad[i].t > best_const + 1e-18L) {
                filtered.push_back(quad[i]);
            }
        }
        quad.swap(filtered);
    }

    sort(quad.begin(), quad.end(), [](const ContinuousDish &a, const ContinuousDish &b) {
        return a.t > b.t;
    });

    int c = (int) quad.size();
    vector<long double> pref_a(c + 1, 0), pref_b(c + 1, 0), pref_c(c + 1, 0);
    for (int i = 1; i <= c; i++) {
        long double inv = 1.0L / quad[i - 1].d;
        pref_a[i] = pref_a[i - 1] + inv;
        pref_b[i] = pref_b[i - 1] + quad[i - 1].t * inv;
        pref_c[i] = pref_c[i - 1] + quad[i - 1].t * quad[i - 1].t * inv / 2.0L;
    }

    if (best_const > NEG_INF / 2 && c == 0) {
        for (int x = 1; x <= W; x++) {
            cont_best[x] = best_const * x;
        }
        return;
    }

    for (int k = 1; k <= c; k++) {
        long double low = pref_b[k] - pref_a[k] * quad[k - 1].t;
        if (low < 0) {
            low = 0;
        }

        long double next_t;
        if (k < c) {
            next_t = quad[k].t;
            if (best_const > NEG_INF / 2) {
                next_t = max(next_t, best_const);
            }
        } else if (best_const > NEG_INF / 2) {
            next_t = best_const;
        } else {
            next_t = -1e100L;
        }

        long double high;
        if (next_t < -1e90L) {
            high = W;
        } else {
            high = pref_b[k] - pref_a[k] * next_t;
        }

        int left = (int) ceill(low - 1e-18L);
        int right = (int) floorl(high + 1e-18L);
        if (left < 0) {
            left = 0;
        }
        if (right > W) {
            right = W;
        }

        for (int x = left; x <= right; x++) {
            long double lambda = (pref_b[k] - x) / pref_a[k];
            long double val = pref_c[k] - lambda * lambda * pref_a[k] / 2.0L;
            cont_best[x] = max(cont_best[x], val);
        }
    }

    if (best_const > NEG_INF / 2) {
        long double x0 = pref_b[c] - pref_a[c] * best_const;
        if (x0 < 0) {
            x0 = 0;
        }
        long double base = pref_c[c] - best_const * best_const * pref_a[c] / 2.0L;
        int start = (int) ceill(x0 - 1e-18L);
        if (start < 0) {
            start = 0;
        }
        for (int x = start; x <= W; x++) {
            cont_best[x] = max(cont_best[x], base + (x - x0) * best_const);
        }
    }
}

void dfs_discrete(int idx, int used_weight, long double cur_value) {
    if (used_weight > W) {
        return;
    }
    if (idx == (int) discrete_dishes.size()) {
        if (continuous_dishes.empty()) {
            if (used_weight == W) {
                answer = max(answer, cur_value);
            }
        } else if (cont_best[W - used_weight] > NEG_INF / 2) {
            answer = max(answer, cur_value + cont_best[W - used_weight]);
        }
        return;
    }

    DiscreteDish dish = discrete_dishes[idx];
    int max_cnt = (W - used_weight) / dish.weight;
    long double add = 0;

    for (int cnt = 0; cnt <= max_cnt; cnt++) {
        dfs_discrete(idx + 1, used_weight + cnt * dish.weight, cur_value + add);
        add += dish.t - cnt * dish.d;
    }
}

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

    // brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
    // 暴力枚举每种离散菜取多少份，再把剩余重量交给连续菜做解析最优分配。
    cin >> n >> W;
    for (int i = 1; i <= n; i++) {
        char type;
        cin >> type;
        if (type == 'D') {
            DiscreteDish dish;
            cin >> dish.weight >> dish.t >> dish.d;
            discrete_dishes.push_back(dish);
        } else {
            ContinuousDish dish;
            cin >> dish.t >> dish.d;
            continuous_dishes.push_back(dish);
        }
    }

    solve_continuous_part();

    answer = NEG_INF;
    dfs_discrete(0, 0, 0);

    if (answer <= NEG_INF / 2) {
        cout << "impossible\n";
    } else {
        cout << fixed << setprecision(9) << (double) answer << '\n';
    }

    return 0;
}

这题要把离散菜和连续菜拆开看。

离散菜部分：
如果某道离散菜每份重量是 c，取 k 份的总收益是：

k t - Δt * k(k-1) / 2

它是一个关于 k 的凹二次函数，所以属于“凹费用完全背包”。
按重量模 c 分组后，可以把转移式整理成斜率单调的直线查询，用单调队列做到每道菜 $O(W)$ 。

连续菜部分：
设剩余重量是 X。
每道连续菜的收益函数都是：

f_i(x) = t_i x - Δt_i x^2 / 2

在 sum x_i = X 下最大化这些凹函数和，最优解满足所有真正被取到的菜具有相同边际收益。
于是连续菜的最优值是一个分段二次函数，可以按 t_i 排序后一次性预处理出每个整数剩余重量 0..W 的最优值。

最后枚举离散菜用了多少整数重量 used，答案就是：

离散最优[used] + 连续最优[W-used]

如果根本没有连续菜，那就必须由离散菜恰好凑出 W，否则输出 impossible。

DP 转移方程

核心状态：

disc[w] 为离散菜重量 w 的最大美味

核心转移：

ans=max_w disc[w]+cont[W-w]

答案收束：

W 重量恰好凑满的最大值

代码

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
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248#include <bits/stdc++.h>
using namespace std;

const long double NEG_INF = -1e100L;

struct DiscreteDish {
    int weight;
    long double t;
    long double d;
};

struct ContinuousDish {
    long double t;
    long double d;
};

struct Line {
    long double m, b;
};

int n, W;
vector<DiscreteDish> discrete_dishes;
vector<ContinuousDish> continuous_dishes;
vector<long double> dp, ndp;
vector<long double> cont_best;

long double value_of_line(const Line &line, long double x) {
    return line.m * x + line.b;
}

long double intersect_x(const Line &a, const Line &b) {
    return (a.b - b.b) / (b.m - a.m);
}

void add_line(deque<Line> &q, Line cur) {
    if (!q.empty() && fabsl(q.back().m - cur.m) < 1e-18L) {
        if (q.back().b >= cur.b) {
            return;
        }
        q.pop_back();
    }
    while (q.size() >= 2) {
        Line a = q[q.size() - 2];
        Line b = q[q.size() - 1];
        if (intersect_x(a, b) >= intersect_x(b, cur) - 1e-18L) {
            q.pop_back();
        } else {
            break;
        }
    }
    q.push_back(cur);
}

void solve_discrete_knapsack() {
    dp.assign(W + 1, NEG_INF);
    dp[0] = 0;

    for (size_t idx = 0; idx < discrete_dishes.size(); idx++) {
        int cost = discrete_dishes[idx].weight;
        long double t = discrete_dishes[idx].t;
        long double d = discrete_dishes[idx].d;

        ndp = dp;

        for (int r = 0; r < cost; r++) {
            vector<long double> old;
            for (int pos = r; pos <= W; pos += cost) {
                old.push_back(dp[pos]);
            }

            deque<Line> q;
            int cnt = (int) old.size();

            for (int m = 0; m < cnt; m++) {
                if (old[m] > NEG_INF / 2) {
                    Line cur;
                    cur.m = d * m;
                    cur.b = old[m] - d * m * m / 2.0L - (t + d / 2.0L) * m;
                    add_line(q, cur);
                }

                while (q.size() >= 2 && value_of_line(q[0], m) <= value_of_line(q[1], m) + 1e-18L) {
                    q.pop_front();
                }

                if (!q.empty()) {
                    long double best =
                        -d * m * m / 2.0L + (t + d / 2.0L) * m + value_of_line(q[0], m);
                    int pos = r + m * cost;
                    ndp[pos] = max(ndp[pos], best);
                }
            }
        }

        dp.swap(ndp);
    }
}

void solve_continuous_part() {
    cont_best.assign(W + 1, NEG_INF);
    cont_best[0] = 0;

    if (continuous_dishes.empty()) {
        return;
    }

    long double best_const = NEG_INF;
    vector<ContinuousDish> quad;

    for (size_t i = 0; i < continuous_dishes.size(); i++) {
        if (fabsl(continuous_dishes[i].d) < 1e-18L) {
            best_const = max(best_const, continuous_dishes[i].t);
        } else {
            quad.push_back(continuous_dishes[i]);
        }
    }

    if (best_const > NEG_INF / 2) {
        vector<ContinuousDish> filtered;
        for (size_t i = 0; i < quad.size(); i++) {
            if (quad[i].t > best_const + 1e-18L) {
                filtered.push_back(quad[i]);
            }
        }
        quad.swap(filtered);
    }

    sort(quad.begin(), quad.end(), [](const ContinuousDish &a, const ContinuousDish &b) {
        return a.t > b.t;
    });

    int c = (int) quad.size();
    vector<long double> pref_a(c + 1, 0), pref_b(c + 1, 0), pref_c(c + 1, 0);

    for (int i = 1; i <= c; i++) {
        long double inv = 1.0L / quad[i - 1].d;
        pref_a[i] = pref_a[i - 1] + inv;
        pref_b[i] = pref_b[i - 1] + quad[i - 1].t * inv;
        pref_c[i] = pref_c[i - 1] + quad[i - 1].t * quad[i - 1].t * inv / 2.0L;
    }

    if (best_const > NEG_INF / 2 && c == 0) {
        for (int x = 1; x <= W; x++) {
            cont_best[x] = best_const * x;
        }
        return;
    }

    for (int k = 1; k <= c; k++) {
        long double low = pref_b[k] - pref_a[k] * quad[k - 1].t;
        if (low < 0) {
            low = 0;
        }

        long double next_t;
        if (k < c) {
            next_t = quad[k].t;
            if (best_const > NEG_INF / 2) {
                next_t = max(next_t, best_const);
            }
        } else if (best_const > NEG_INF / 2) {
            next_t = best_const;
        } else {
            next_t = -1e100L;
        }

        long double high;
        if (next_t < -1e90L) {
            high = W;
        } else {
            high = pref_b[k] - pref_a[k] * next_t;
        }

        int left = (int) ceill(low - 1e-18L);
        int right = (int) floorl(high + 1e-18L);
        if (left < 0) {
            left = 0;
        }
        if (right > W) {
            right = W;
        }

        for (int x = left; x <= right; x++) {
            long double lambda = (pref_b[k] - x) / pref_a[k];
            long double val = pref_c[k] - lambda * lambda * pref_a[k] / 2.0L;
            cont_best[x] = max(cont_best[x], val);
        }
    }

    if (best_const > NEG_INF / 2) {
        long double x0 = pref_b[c] - pref_a[c] * best_const;
        if (x0 < 0) {
            x0 = 0;
        }
        long double base = pref_c[c] - best_const * best_const * pref_a[c] / 2.0L;
        int start = (int) ceill(x0 - 1e-18L);
        if (start < 0) {
            start = 0;
        }
        for (int x = start; x <= W; x++) {
            cont_best[x] = max(cont_best[x], base + (x - x0) * best_const);
        }
    }
}

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

    cin >> n >> W;
    for (int i = 1; i <= n; i++) {
        char type;
        cin >> type;
        if (type == 'D') {
            DiscreteDish dish;
            cin >> dish.weight >> dish.t >> dish.d;
            discrete_dishes.push_back(dish);
        } else {
            ContinuousDish dish;
            cin >> dish.t >> dish.d;
            continuous_dishes.push_back(dish);
        }
    }

    solve_discrete_knapsack();
    solve_continuous_part();

    long double answer = NEG_INF;

    if (continuous_dishes.empty()) {
        answer = dp[W];
    } else {
        for (int used = 0; used <= W; used++) {
            if (dp[used] <= NEG_INF / 2 || cont_best[W - used] <= NEG_INF / 2) {
                continue;
            }
            answer = max(answer, dp[used] + cont_best[W - used]);
        }
    }

    if (answer <= NEG_INF / 2) {
        cout << "impossible\n";
    } else {
        cout << fixed << setprecision(9) << (double) answer << '\n';
    }

    return 0;
}

复杂度

设总重量为 W。

离散菜部分复杂度 $O(离散菜数量 * W)$
连续菜部分预处理复杂度 $O(连续菜数量 log 连续菜数量 + W)$

总空间复杂度 $O(W)$ 。

总结

这题最关键的是不要把两类菜混在一起做。

离散菜是“凹费用背包”
连续菜是“分段二次最优分配”

拆开以后各自处理，再在总重量上合并，结构就清楚了。

一图流解析

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

P6893 [ICPC 2014 WF] Buffed Buffet

题目描述

You are buying lunch at a buffet. A number of different dishes are available, and you can mix and match them to your heart’s desire. Some of the dishes, such as dumplings and roasted potatoes, consist of pieces of roughly equal size, and you can pick an integral number of such pieces (no splitting is allowed). Refer to these as “discrete dishes.” Other dishes, such as tzatziki or mashed potatoes, are fluid and you can pick an arbitrary real-valued amount of them. Refer to this second type as “continuous dishes.”

Of course, you like some of the dishes more than others, but how much you like a dish also depends on how much of it you have already eaten. For instance, even if you generally prefer dumplings to potatoes, you might prefer a potato over a dumpling if you have already eaten ten dumplings. To model this, each dish $i$ has an initial tastiness $t_ i$ , and a rate of decay of the tastiness $\Delta t_ i$ . For discrete dishes, the tastiness you experience when eating the $n^{th}$ item of the dish is $t_ i - (n-1)\Delta t_ i$ . For continuous dishes, the tastiness you experience when eating an infinitesimal amount $d x$ grams of the dish after already having eaten $x$ grams is $(t_ i - x \Delta t_ i) d x$ . In other words, the respective total amounts of tastiness you experience when eating $N$ items of a discrete dish or $X$ grams of a continuous dish are as follows:

\begin{aligned} \sum _{n=1}^{N} (t_ i - (n-1)\Delta t_ i) & & \text {and} & & \int _{0}^ X (t_ i - x\Delta t_ i) dx \end{aligned}

For simplicity, do not take into account that different dishes may or may not go well together, so define the total tastiness that you experience from a meal as the sum of the total tastinesses of the individual dishes in the meal (and the same goes for the weight of a meal – there are no food antiparticles in the buffet!).

You have spent days of painstaking research determining the numbers $t_ i$ and $\Delta t_ i$ for each of the dishes in the buffet. All that remains is to compute the maximum possible total tastiness that can be achieved in a meal of weight $w$ . Better hurry up, lunch is going to be served soon!

输入格式

The input consists of a single test case. The first line of input consists of two integers $d$ and $w$ ( $1 \le d \le {250}$ and $1 \le w \le {10\, 000}$ ), where $d$ is the number of different dishes at the buffet and $w$ is the desired total weight of your meal in grams.

Then follow $d$ lines, the $i^{th}$ of which describes the $i^{th}$ dish. Each dish description is in one of the following two forms:

A description of the form “D $w_ i$ $t_ i$ $\Delta t_ i$ ” indicates that this is a discrete dish where each item weighs $w_ i$ grams, with initial tastiness $t_ i$ and decay of tastiness $\Delta t_ i$ .

A description of the form “C $t_ i$ $\Delta t_ i$ ” indicates that this is a continuous dish with initial tastiness $t_ i$ and decay of tastiness $\Delta t_ i$ .

The numbers $w_ i$ , $t_ i$ , and $\Delta t_ i$ are integers satisfying $1 \le w_ i \le {10\, 000}$ and $0 \le t_ i, \Delta t_ i \le {10\, 000}$ .

输出格式

Display the maximum possible total tastiness of a meal of weight $w$ based on the available dishes. Give the answer with a relative or absolute error of at most $10^{-6}$ . If it is impossible to make a meal of total weight exactly $w$ based on the available dishes, display impossible.

输入输出样例 #1

输入 #1

text

输出 #1

text

140.500000000

输入输出样例 #2

输入 #2

text

输出 #2

text

149.000000000

输入输出样例 #3

输入 #3

text

输出 #3

text

1impossible

说明/提示

Time limit: 3000 ms, Memory limit: 1048576 kB.

International Collegiate Programming Contest (ACM-ICPC) World Finals 2014

[ICPC 2014 WF] Buffed Buffet

目录

题意

思路

DP 转移方程

代码

复杂度

总结

一图流解析