ZOJ - 3469 Food Delivery（区间DP）

题目大意：有一个餐厅，在X这个位置，送餐速度为v的-1次方，有N个顾客，分别在pos位置，每个顾客都有一个displeasure值，当餐送到该顾客手上时，该顾客的displeasure总值为 displeasure值 ＊ 到手时间

问所有顾客的最小displeasure总值和是多少

解题思路：首先按位置排个序
设dp[i][j][0]为[i,j]这个区间内的所有人都拿到货了，送货员最后停在i这个位置的最小displeasure总值和
dp[i][j][1]为[i,j]这个区间内的所有人都拿到货了，送货员最后停在j这个位置的最小displeasure总值和
下面的AllDispleasure表示的是区间之外的所有displeasure值的总和，因为区间外的所有人都还没有拿到货，所以要（AllDispleasure + 目的地的displeasure） ＊ （送货时间）
那么dp[i][j][0] = min( dp[i][j][0] , dp[i + 1][j][0] + (pos[i + 1] - pos[i]) * (AllDiapleasure + displeasure[i]))

dp[i][j][0] = min( dp[i][j][0] , dp[i + 1][j][1] + (pos[j] - pos[i]) * (AllDiapleasure + displeasure[i]))

dp[i][j][1] = min( dp[i][j][1] , dp[i][j - 1][0] + (pos[j] - pos[i]) * (AllDiapleasure + displeasure[j]))

dp[i][j][0] = min( dp[i][j][1] , dp[i][j - 1][1] + (pos[j] - pos[j - 1]) * (AllDiapleasure + displeasure[j]))
最后答案是min(dp[1][n - 1][0], dp[1][n - 1][1]) * v

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;

struct Node{
    int pos, b;
}node[N];

int n, v, start;
int Sum[N], dp[N][N][2];

bool cmp(const Node &a, const Node &b) {
    return a.pos < b.pos;
}

void init() {
    for (int i = 1; i <= n; i++) 
        scanf("%d%d", &node[i].pos, &node[i].b);
    n++;
    node[n].pos = start; node[n].b = 0;
    n++;
    sort(node + 1, node + n, cmp);
    Sum[0] = 0;

    for (int i = 1; i < n; i++)
        Sum[i] = Sum[i - 1] + node[i].b;
}

int Displaysure(int l, int r) {
    if (l > r) return 0;
    return Sum[r] - Sum[l - 1]; 
}

void solve() {
    memset(dp, 0x3f, sizeof(dp));

    int startPos;
    for (int i = 1; i < n; i++) {
        if (node[i].pos == start) {
            startPos = i;
            break;
        }
    }

    dp[startPos][startPos][0] = dp[startPos][startPos][1] = 0;
    for (int i = startPos; i >= 1; i--)
        for (int j = startPos; j < n; j++) {
            if (i == j) continue;
            int t = Displaysure(1, i - 1) + Displaysure(j + 1, n - 1); 
            dp[i][j][0] = min(dp[i][j][0], dp[i + 1][j][0] + (node[i + 1].pos - node[i].pos) * (t + node[i].b));
            dp[i][j][0] = min(dp[i][j][0], dp[i + 1][j][1] + (node[j].pos - node[i].pos) * (t + node[i].b));
            dp[i][j][1] = min(dp[i][j][1], dp[i][j - 1][0] + (node[j].pos - node[i].pos) * (t + node[j].b));
            dp[i][j][1] = min(dp[i][j][1], dp[i][j - 1][1] + (node[j].pos - node[j - 1].pos) * (t + node[j].b));
        }
    printf("%d\n", min(dp[1][n - 1][0], dp[1][n - 1][1]) * v);
}

int main() {
    while (scanf("%d%d%d", &n, &v, &start) != EOF) {
        init();
        solve();
    }
    return 0;
}