P2616 USACO10 JANBuying Feed, II S

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

一. 变量声明：

  • WW：代替题目中的 KK，到家时应带的饲料吨数，相当于背包中的背包最大承重（weight）。
  • nn：代替题目中的 NN，商店数量，相当于背包问题中的物品数。
  • xix_i：同题目中的 xix_i。
  • wiw_i：代替题目中的 fif_i，商店 ii 食物数量。
  • viv_i：代替题目中的 cic_i，商店 ii 食物单价。

二. 思路

1. 思考解法

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

所以考虑背包 DP。

2. 初始状态

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

3. 结束状态

dhome⁡,Wd_{\operatorname{home},W} （home⁡\operatorname{home}：见代码和代码中的注释）

4. 确定状态转移方程

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

本题就是一道改装版的多重背包问题，就加了一个转移花费，转移花费怎么求呢？ii 店与上一家店距离差为 xi−xi−1x_i-x_{i-1}，若在 ii 号店买的食物份数为 kk ，在 ii 店购物后车上的食物份数为 jj（jj 和 kk 这两个量都是 for 循环枚举出来的），则这段路上车辆运送的食物数为 j−kj-k。转移花费就是 (xi−xi−1)×(j−k)(x_i-x_{i-1})\times (j-k)。

综上所述，状转方程：di,j=min⁡k=0k⩽wi{di−1,j−k+(xi−xi−1)×(j−k)+vi×k}d_{i,j}=\min_{k=0}^{k\leqslant w_i}\left\{d_{i-1,j-k}+(x_i-x_{i-1})\times (j-k)+v_i\times k\right\}

三. 代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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]);
}