Luogu P4544 [USACO10NOV]Buying Feed G

P4544 USACO10NOV Buying Feed G

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

一. 变量声明：

• $W$：代替题目中的 $K$，到家时应带的饲料吨数，相当于背包中的背包最大承重（weight）。
• $n$：代替题目中的 $N$，商店数量，相当于背包问题中的物品数。
• $x_i$：同题目中的 $x_i$。
• $w_i$：代替题目中的 $f_i$，商店 $i$ 食物数量。
• $v_i$：代替题目中的 $c_i$，商店 $i$ 食物单价。

二. 思路

1. 思考解法

• 路线上后面的商店不会影响路线前半部分的最优解，符合无后效性。
• 有最大容量 $W$，有可选择的物品，每个物品有重量和价值，明显是背包类问题。

所以考虑背包 DP。

2. 初始状态

$d_{i,j}=\begin{cases} 0&(i=0~\land~j=0)\\ \infty&(else) \end{cases}$

3. 结束状态

$d_{\operatorname{home},W}$ （$\operatorname{home}$：见代码和代码中的注释）

4. 确定状态转移方程

$d_{i,j}$：已经经过前 $i$ 个商店（已到 $i$ 号商店买了东西但还没有往 $i+1$ 号走）且恰好一共买了 $j$ 份食物时最少花费的费用。

本题就是一道改装版的多重背包问题，就加了一个转移花费，转移花费怎么求呢？$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}\left\{d_{i-1,k}+(x_i-x_{i-1})\times k^2+v_i\times (j-k)\right\}$

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

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

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

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

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

$$\Longrightarrow d_{i,j}=\min_{k=0}^{k\leqslant j}\left\{d_{i-1,k}+(x_i-x_{i-1})\times k^2-v_i\times k\right\}+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]);
}