Luogo P2616 [USACO10JAN]Buying Feed, II S

· · 题解

放在前面：为对应“普及-”的难度，本文讲解的是 O(nW^2) 复杂度的朴素 DP，如想挑战更高难度请进 Here，并欢迎大家来该题题解看我的另一篇博客上的 O(nW) 解法。

零. 安利：

安利一下我的博客。

一. 变量声明：

二. 思路

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$（$j$ 和 $k$ 这两个量都是 for 循环枚举出来的），则这段路上车辆运送的食物数为 $j-k$。转移花费就是 $(x_i-x_{i-1})\times (j-k)$。 **综上所述，状转方程**：$d_{i,j}=\min_{k=0}^{k\leqslant w_i}\{{d_{i-1,j-k}+(x_i-x_{i-1})\times (j-k)+v_i\times k}\}

三. 代码

代码中有一些例如构造函数和重载运算符一样的技巧，这些暂时不会也不妨碍理解算法，只需看 main 函数中的内容就行了。

#include<bits/stdc++.h>

using namespace std;

#define re register

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;  
}

inline int min(int a, int 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 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：当前阶段是在哪个店 
        for (re int j = W; j >= 0; --j) {    //j：当前状态要求车上有多少饲料 
            for (re int k = 0; k <= shop[i].w; ++k) {    //k：当前转移中要从本店买多少饲料 
                if (j < k) continue;
                d[i][j] = min(d[i][j], d[i - 1][j - k] + (shop[i].x - shop[i - 1].x) * (j - k) + k * shop[i].v);
            }
        }
    }
    printf("%d", d[n + 1][W]);
}