自动搬运

查看原文

来自洛谷，原作者为

	FangZeLi 宁愿重伤也不愿悲伤，让伤痕变成了我的徽章，刺在我心脏，永远不忘。

搬运于2025-08-24 22:25:00，当前版本为作者最后更新于2021-04-18 16:14:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Link

P6893 [ICPC2014 WF]Buffed Buffet

Solution

显然这个问题看着就非常背包。

注意到食物其实分成两类，贡献分别是离散和连续的。

回想一下我们初学DP时，有个非常重要的结论：01背包不可以贪心，但是分数背包可以。

那么作用到这题上，我们分开考虑这两种物品。

对于不连续的，我们设计一个背包；对于连续的，我们设计一个贪心。

先考虑相对复杂一点的背包：

设 $f_{i,j}$ 表示前 $i$ 种菜吃了 $j$ 克时可获得的最大美味值，则有转移：

$$f_{i,j}=\max_{0\le k \le \lfloor\frac{j}{w_i}\rfloor}(f_{i-1, j - kw_i}+\sum_{n=1}^k(t_i - (n - 1)\Delta t_i)) $$

直接转移要枚举 $i$，$j$，$k$，复杂度大概是 ${\mathcal O}(dw^2)$。肯定是过不去的，T​飞了，那么肯定是考虑优化。

这个背包虽然是两维的，但是熟悉背包的你肯定知道，$i$ 这一维实际上是“假”的。或者说，$i$某种程度上只起到了一个标记版本的作用。那么这样的话，我们就可以往一维DP的各种优化的角度考虑。

状态上是不太能压缩了。考虑优化转移的过程，利用一下决策单调性，先把式子拆一下：

$$f_{i,j}=\max_{0\le k \le \lfloor\frac{j}{w_i}\rfloor}(f_{i-1, j - kw_i}+kt_i-\dfrac{\Delta t_ik(k-1)}2) $$

然后你发现这个东西长得非常的斜率优化，于是我们往这个方面考虑：

$$f_j = \max_{0\le k \le \lfloor\frac{j}{w}\rfloor}(g_{j - kw}+kt-\dfrac{\Delta tk(k-1)}2) $$

我们把下标关于$w_i$的同余类分开考虑，变换下标，记 $i' = \lfloor\dfrac{i}{w}\rfloor$，则有：

$$\begin{aligned} f_j &= \max_{0\le i \le j}(g_i + (j - i)t - \dfrac{\Delta t(j-i)(j-i-1)}2) \\ &= \max_{0\le i \le j}(g_i + jt - it - \dfrac{\Delta t}2(j^2-2ij+i^2-j+i)) \\ &= \max_{0\le i \le j}(g_i - it - \dfrac{\Delta t}2i(i+1) + \Delta tij) + jt - \dfrac{\Delta t}2j(j-1) \\ g_i - it - \dfrac{\Delta t}2i(i + 1) &= - \Delta tj \times i + f_j - jt + \dfrac{\Delta t}2j(j-1) \end{aligned} $$

这个式子就可以斜率优化做了，复杂度 $\mathcal{O}(dw)$。

然后考虑连续的贪心部分。

我们每次都取当前美味值最大的，然后，当两种食品的美味值相等的时候，我们“合并”这两种食品。

具体的，当两种美味值分别为$a$，$b$的连续食品合并的时候，新食品的美味值就是 $\dfrac1{\frac{1}a + \frac{1}b}$，那么这部分的复杂度是 $\mathcal{O}(d + w)$。

最后枚举下多少给离散，多少给连续，就做完了。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <deque>

#define _D 260
#define _W 10010
#define _INF 1e18
#define _EPS 1e-10

struct C {
	int t, dt;
};
struct D {
	int w, t, dt;
};

bool inline operator <(const C& left, const C& right) {
	return left.t > right.t;
}

int d, w;

int ccnt, dcnt;
C fdc[_D];
D fdd[_D];

namespace workD {
	int curt, curdt, curw, r;
	double f[_W], tmp[_W];
	
	std::deque<int> q;
	
	double inline x(int p) {
		return 1.0 * p;
	}
	double inline y(int p) {
		return tmp[p * curw + r] - 1.0 * p * curt - 0.5 * curdt * p * (p + 1);
	}
	double inline slope(int left, int right) {
		double lx = x(left), rx = x(right), ly = y(left), ry = y(right);
		return (ry - ly) / (rx - lx == 0 ? _EPS : 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) {
		curw = wi, curt = t, curdt = dt;
		for (int i = 1; i <= w; i++) {
			tmp[i] = f[i];
			f[i] = -_INF;
		}
		for (r = 0; r < wi; r++) {
			q.clear();
			for (int j = 0; j * wi + r <= w; j++) {
				ins(j);
				del(-1.0 * dt * j);
				int i = q.front();
				f[j * wi + r] = std::max(f[j * wi + r], tmp[i * wi + r] + 1.0 * (j - i) * t - 1.0 * (j - i) * (j - i - 1) / 2 * dt);
			}
		}
	}

	void calc() {
		for (int i = 1; i <= w; i++) {
			f[i] = -_INF;
		}
		for (int i = 1; i <= dcnt; i++) {
			add(fdd[i].w, fdd[i].t, fdd[i].dt);
		}
	}
}
namespace workC {
	double f[_W];

	void calc() {
		if (ccnt == 0) {
			for (int i = 1; i <= w; i++) {
				f[i] = -_INF;
			}
			return;
		}
		std::sort(fdc + 1, fdc + ccnt + 1);
		int pt = 1;
		double curv = fdc[1].t, curdt = fdc[1].dt, curw = 0, cursum = 0;
		pt++;
		for (int i = 1; i <= w; i++) {
			while (curw < 1.0 * i) {
				if (pt > ccnt || curv - curdt * (i - curw) > 1.0 * fdc[pt].t) {
					cursum += curv * (i - curw) - 0.5 * (i - curw) * (i - curw) * curdt;
					curv -= curdt * (i - curw), curw = i;
				} else {
					double q = (curv - 1.0 * fdc[pt].t) / curdt;
					cursum += curv * q - 0.5 * q * q * curdt;
					curv = fdc[pt].t, curw += q;
					curdt = 1.0 / (1.0 / curdt + 1.0 / (fdc[pt].dt != 0 ? fdc[pt].dt : _EPS));
					pt++;
				}
			}
			f[i] = cursum;
		}
	}
}

int main() {
	scanf("%d%d", &d, &w);
	while (d--) {
		char tp[10];
		scanf("%s", tp);
		switch (tp[0]) {
			case 'D':
				++dcnt;
				scanf("%d%d%d", &fdd[dcnt].w, &fdd[dcnt].t, &fdd[dcnt].dt);
				break;
			case 'C':
				++ccnt;
				scanf("%d%d", &fdc[ccnt].t, &fdc[ccnt].dt);
				break;
		}
	}
	workC::calc(), workD::calc();
	double ans = -_INF;
	for (int i = 0; i <= w; i++) {
		ans = std::max(ans, workC::f[i] + workD::f[w - i]);
	}
	if (ccnt == 0 && ans < -1e16) {
		puts("impossible");
	} else {
		printf("%.10lf\n", ans);
	}
	return 0;
}

Inspiration

我认为这一道题目处理方法整体来说比较自然，没有太过于需要“想象力”的步骤，基本上说是按部就班。

核心结论：

• 背包有一维实际上不重要，故可以看成一维的然后斜率优化
• 两种连续的食品在美味值相同时可以合并