P6893题解

· · 题解

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

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

核心结论：