Luogu P4544 [USACO10NOV]Buying Feed G

· · 题解

放在前面：本方法时间复杂度为 O(nW) ，单调队列优化 DP。本题还有一道弱化版，欢迎大佬切完这题顺便把那题也切了，并欢迎大家来该题题解看我的另一篇博客。

零. 安利：

安利一下我的博客。

一. 变量声明：

二. 思路

1. 思考解法

所以考虑背包 DP。

2. 初始状态
d_{i,j}=\begin{cases} 0~~~~~~~~~(i=0~\land~j=0)\\ \infty~~~~~~~(else) \end{cases}
3. 结束状态
##### 4. 确定状态转移方程 $d_{i,j}$：已经经过前 $i$ 个商店（已到 $i$ 号商店买了东西但还没有往 $i+1$ 号走）且恰好一共买了 $j$ 份食物时最少花费的费用。 本题就是一道改装版的[多重背包问题](https://www.luogu.com.cn/problem/P1776)，就加了一个转移花费，转移花费怎么求呢？$i$ 店与上一家店距离差为 $x_i-x_{i-1}$，若在 $i$ 号店之前买的食物份数一共为 $k$ ，在 $i$ 店购物后车上的食物份数为 $j$，则这段路上车辆运送的食物数为 $k$。转移花费就是 $(x_i-x_{i-1})\times k^2$。 综上所述，朴素状转方程：$d_{i,j}=\min_{k=0}^{k\leqslant j}\{{d_{i-1,k}+(x_i-x_{i-1})\times k^2+v_i\times (j-k)}\}

5. 单调队列优化（重点）

枚举 i 复杂度为 O(n)，枚举 j 复杂度为 O(W)，枚举 k 最坏情况下复杂度也是 O(W)。总复杂度 O(nW^2) 显然会超。那么让我们观察一下状转方程：

~~~~~~~~d_{i,j}=\min_{k=0}^{k\leqslant j}\{{d_{i-1,k}+(x_i-x_{i-1})\times k^2+v_i\times (j-k)}\} \Longrightarrow d_{i,j}=\min_{k=0}^{k\leqslant j}\{{d_{i-1,k}+(x_i-x_{i-1})\times k^2-v_i\times k+v_i\times j}\}

重点一 ：观察上面这个拆了个括号的方程，左边是我们要去求的状态，在该状态下，i 和 j 是已知的，因为该状态就是由 i 和 j 定义的，i 和 j 在一个具体的状态下为常量（或者换一种解释：i 和 j 是用 for 循环枚举出来的，所以我们当然知道他的值）。所以我们可以将 v_i\times j 提出括号。可得：

\Longrightarrow d_{i,j}=\min_{k=0}^{k\leqslant j}\{{d_{i-1,k}+(x_i-x_{i-1})\times k^2-v_i\times k}\}+v_i\times j

重点二：这个方程中的变量只有 k，而又有 k\leqslant j，因为在 i 店购物后的食物数不可能低于购物前。那么我们就可以使用单调队列优化。单调队列中存放的就是 \min 内的部分 d_{i-1,k}+(x_i-x_{i-1})\times k^2-v_i\times k （在这里我们把它称作 calc_{i,k}），对于每一个 i ，将 j 从 0 到 W 枚举一遍，对于每个 j 先将它作为 k 计算 calc_{i,k} 并放到单调队列中，再先计算状态 d_{i.j}。

三. 代码

#include<bits/stdc++.h>

using namespace std;

#define re register
#define int long long

const int MAXn = 500;
const int MAXW = 10000;

template <class T> 
inline void read(T &a) {
    register char c;while (c = getchar(), c < '0' || c >'9');register T x(c - '0');while (c = getchar(), c >= '0' && c <= '9')x = (x << 1) + (x << 3) + c - '0';a = x;  
}

template <class T>
inline T min(T a, T b) {
    return a < b ? a : b;
}

struct Shop {
    int x;
    int w;
    int v;

    Shop(): x(0), w(0), v(0){}
    Shop(int x_, int w_, int v_): x(x_), w(w_), v(v_) {}
    inline bool operator < (Shop &a) {
        return this->x < a.x;
    }
};

Shop shop[MAXn + 10];
int W, n, d[MAXn + 10][MAXW + 10];
int head, tail, que[MAXW + 10];

inline int calc(int i, int k) {
    return d[i - 1][k] + (shop[i].x - shop[i - 1].x) * k * k - shop[i].v * k;
}

signed main() {
    int E;
    read(W), read(E), read(n);
    shop[0] = Shop(0, 0, 0);    //本人将起点和终点（家）时当做食物数为 0 的商店，这样能避免特判，所以“home”就是n+1
    for (re int i = 1, x, w, v; i <= n; ++i) {
        read(x), read(w), read(v);
        shop[i] = Shop(x, w, v);
    }
    shop[n + 1] = Shop(E, 0, 0);    //同上
    sort(shop, shop + n + 2);
    memset(d, 0x3f, sizeof(d));
    d[0][0] = 0;
    for (re int i = 1; i <= n + 1; ++i) {    //i：当前阶段是在哪个店 
        head = 1; tail = 0;
        for (re int j = 0; j <= W; ++j) {    //j：当前状态要求在此处商店购买后车上有多少饲料
            while (calc(i, que[tail]) > calc(i, j) && head <= tail)
                --tail;
            if (j - que[head] > shop[i].w && head <= tail)
                ++head;
            que[++tail] = j;
            d[i][j] = calc(i, que[head]) + shop[i].v * j;           
        }
    }
    printf("%lld", d[n + 1][W]);
}