Luogu P6893 [ICPC 2014 WF] Buffed Buffet 题解

01背包不可以贪心，但是分数背包可以。

分别考虑两种物品然后枚举合并。

对于 D 类食物，令 \(f(i, j)\) 表示前 \(i\) 种菜吃了 \(j\)​ 克时的最大美味值：

\[\begin{aligned} f(i, j) &= \max_{0 \leq k \leq \lfloor \frac{j}{w_i} \rfloor} \left( f(i - 1, j - kw_i) + \sum_{n = 1}^{k}(t_i - (n - 1) \Delta t_i) \right) \\ f(i, j) &= \max_{0 \leq k \leq \lfloor \frac{j}{w_i} \rfloor} \left( f(i - 1, j - kw_i) + kt_i - \frac{\Delta x_i \times k(k - 1)}{2} \right) \end{aligned} \]

注意到 \(i\) 这一维可以压缩掉，处理第 \(i\) 种菜时令 \(g(i)\) 表示前 \(i - 1\) 个物品的结果，算完第 \(i\) 个物品之后更新到 \(f\) 上去就可以。也就是说，对于单个物品 \((w, t, \Delta t)\)，转移化简为：

\[f(j) = \max_{0 \leq k \leq \lfloor \frac{j}{w} \rfloor} \left( g(j - kw) + kt - \frac{\Delta t \cdot k(k - 1)}{2} \right) \]

考虑怎么搞掉这个除法下取整，按同余类来分离，将下标按照除以 \(w\) 的余数分类处理。

令 \(j = j'w + r\)，其中 \(0 \leq r \lt w\)，则 \(j - kw = (j' - k)w + r\)，设 \(i = j' - k\)，则有：

\[f(j'w + r) = \max_{0 \leq i \leq j'} \left( g(iw + r) + (j' - i)t - \frac{\Delta t \cdot (j' - i)(j' - i - 1)}{2} \right) \]

展开上面这个式子，重新整理：

\[\begin{aligned} f(j'w + r) &= \max_{i} \left( g(iw + r) + (j' - i)t - \frac{\Delta t}{2}({j'}^2 - 2ij' - j' + i) \right) \\ &= \max_{i} \left( g(iw + r) - it - \frac{\Delta t}{2} i(i + 1) + \Delta t i j' \right) + j't - \frac{\Delta t}{2} j'(j' - 1) \end{aligned} \]

注意到后面抽离出来的东西和 \(i\) 无关，考虑对这个 \(f\) 构造点和斜率，令 \(X(i) = i, Y(i) = g(iw + r) - it - \frac{\Delta t}{2} i(i + 1)\)，有：

\[f(j'w + r) = \max_{i} (Y(i) - (-\Delta t j') \times X(i)) + R \]

其中 \(R\) 为无关 \(i\) 常数，这等价于在平面的点 \((X(i), Y(i))\) 中找到使得直线 \(y = kx + b\) 的截距 \(b\) 最大的点，其中斜率 \(k = -\Delta t j'\)，由于 \(\Delta t \gt 0\)，\(j'\) 递增，\(k\) 递增，单调队列维护凸包。每个决策点 \(i\) 对应点 \((i, Y(i))\)，随着 \(j'\) 增大 \(k\) 会负得越来越多越来越陡，最优决策点在凸包上移动。复杂度降到了 \(O(w)\)。

考虑对 C 类食品的贪心。每次取当前收益最大的，当两种物品的收益 \(x, y\) 相等时考虑合并得到收益为 \(\frac{1}{\frac{1}{x} + \frac{1}{y}}\)，这一部分的复杂度为 \(O(d + w)\)。

上面说到的枚举合并指的是枚举划分多少给 C 类剩下的给 B 类。

#include <bits/stdc++.h>using i64 = long long;struct C {int t, dt;
};struct D {int w, t, dt;
};bool inline operator<(const C& a, const C& b) {return a.t > b.t;
}int d, w;
int cc, dc;
std::vector<C> fc;
std::vector<D> fd;namespace Sol1 {int ct, cd, cw, r;std::vector<double> f, g;std::deque<int> q;double x(int p) {return p;}double y(int p) {return g[p * cw + r] - p * ct - 0.5 * cd * p * (p + 1);}double slope(int l, int r) {double lx = x(l), rx = x(r), ly = y(l), ry = y(r);return (ry - ly) / (rx - lx == 0 ? 1e-10 : rx - lx);}void ins(int p) {while (q.size() > 1 && slope(q[q.size() - 2], q.back()) < slope(q[q.size() - 2], p)) q.pop_back();q.push_back(p);}void del(double k) {while (q.size() > 1 && slope(q.front(), q[1]) > k) q.pop_front();}void add(int wi, int t, int dt) {cw = wi, ct = t, cd = dt;for (int i = 1; i <= w; i++) {g[i] = f[i];f[i] = -1e18;}for (r = 0; r < cw; r++) {q.clear();for (int j = 0; j * cw + r <= w; j++) {ins(j);del(-dt * j);int i = q.front();f[j * cw + r] = std::max(f[j * cw + r], g[i * cw + r] + (j - i) * t - 0.5 * (j - i) * (j - i - 1) * dt);}}}void calc() {f.assign(w + 1, -1e18);g.resize(w + 1);for (int i = 1; i <= dc; i++) add(fd[i].w, fd[i].t, fd[i].dt);}
}namespace Sol2 {std::vector<double> f;void calc() {f.resize(w + 1);if (cc == 0) {for (int i = 1; i <= w; i++) f[i] = -1e18;return;}std::sort(fc.begin() + 1, fc.begin() + cc + 1);int p = 1;double cur = fc[1].t, cdt = fc[1].dt, cw = 0, sum = 0;p++;for (int i = 1; i <= w; i++) {while (cw < i) {if (p > cc || cur - cdt * (i - cw) > fc[p].t) {sum += cur * (i - cw) - 0.5 * (i - cw) * (i - cw) * cdt;cur -= cdt * (i - cw), cw = i;} else {double q = (cur - fc[p].t) / cdt;sum += cur * q - 0.5 * q * q * cdt;cur = fc[p].t, cw += q;cdt = 1.0 / (1.0 / cdt + 1.0 / (fc[p].dt != 0 ? fc[p].dt : 1e-10));p++;}}f[i] = sum;}}
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cin >> d >> w;fc.resize(d + 1);fd.resize(d + 1);while (d--) {char tp[10];std::cin >> tp;if (tp[0] == 'D') {++dc;std::cin >> fd[dc].w >> fd[dc].t >> fd[dc].dt;} else {++cc;std::cin >> fc[cc].t >> fc[cc].dt;}}Sol1::calc();Sol2::calc();double ans = -1e18;for (int i = 0; i <= w; i++) ans = std::max(ans, Sol2::f[i] + Sol1::f[w - i]);if (cc == 0 && ans < -1e16) std::cout << "impossible\n";else std::cout << std::fixed << std::setprecision(10) << ans << "\n";return 0;
}