ZOJ Food Delivery：區間 DP 最小化不愉快指數

區間 DP 狀態

排序後餐廳位置為分界點 pos。
dp[l][r][0/1]：已送完 [l, r] 區間內所有顧客，送餐員當前在 l(0) 或 r(1) 位置的最小累積不愉快。
區間外顧客的 b 總和記為 delay，每移動一段距離 d，增加 delay × d / V（最後統一乘 V 避免小數）。

轉移方程

dp[l][r][0] = min(
    dp[l+1][r][0] + (a[l+1].x - a[l].x) * (delay + a[l].b),
    dp[l+1][r][1] + (a[r].x - a[l].x) * (delay + a[l].b)
);
dp[l][r][1] = min(
    dp[l][r-1][0] + (a[r].x - a[l].x) * (delay + a[r].b),
    dp[l][r-1][1] + (a[r].x - a[r-1].x) * (delay + a[r].b)
);

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1010, INF = 1<<29;
struct Node { int x, b; } a[MAXN];
int dp[MAXN][MAXN][2], sumB[MAXN];
int delay(int l, int r) { return l>r?0:sumB[r]-sumB[l-1]; }
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, V, X;
    while (cin >> n >> V >> X) {
        for (int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].b;
        a[++n] = {X, 0}; // 餐廳作為一個特殊點
        sort(a+1, a+n+1, [](Node u, Node v){ return u.x < v.x; });
        int pos = 1; while (a[pos].x != X) ++pos;
        sumB[0] = 0;
        for (int i = 1; i <= n; ++i) sumB[i] = sumB[i-1] + a[i].b;
        // 初始化 dp 為 INF
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dp[i][j][0] = dp[i][j][1] = INF;
        dp[pos][pos][0] = dp[pos][pos][1] = 0;
        for (int len = 2; len <= n; ++len)
            for (int l = max(1, pos-len+1); l <= pos; ++l) {
                int r = l + len - 1; if (r > n) continue;
                int d = delay(1, l-1) + delay(r+1, n);
                if (l < pos) {
                    dp[l][r][0] = min(
                        dp[l+1][r][0] + (a[l+1].x - a[l].x) * (d + a[l].b),
                        dp[l+1][r][1] + (a[r].x - a[l].x) * (d + a[l].b)
                    );
                }
                if (r > pos) {
                    dp[l][r][1] = min(
                        dp[l][r-1][0] + (a[r].x - a[l].x) * (d + a[r].b),
                        dp[l][r-1][1] + (a[r].x - a[r-1].x) * (d + a[r].b)
                    );
                }
            }
        cout << (ll)min(dp[1][n][0], dp[1][n][1]) * V << '\n';
    }
    return 0;
}

複雜度

O(n²) 狀態，每狀態 O(1) 轉移，n ≤ 1000 約 10⁶ 操作，極快。答案最後乘 V 避免中間除法精度問題。