当上CEO之我在兰州帝国

形式化题目

$n$ 个客户在位置 $p_i$ ，每人有等待系数 $A_i$ 与随时间增长的需求 $d_i$ 。无人机从 $s$ 出发、速度 $v$ ，逐个送达（顺序任意）；客户的代价随未送达时长线性增长。求总代价（含 $\sum A_i$ 部分）的最小值。

正解

思路

1. 区间 DP 形态

最优路线在位置轴上连续推进（往返交错可交换性），按位置排序后状态为 $(l,r,\text{端点})$ ：已送完连续区间 $[l,r]$ 、无人机停在左或右端点。

每次向外扩展一位：飞行距离 $=|x_{\text{new}}-x_{\text{端点}}|$ ，飞行期间所有未送客户的 $d$ 同时累积 → 扩展代价 $= \bigl(\sum_{\text{未送}} d_i\bigr)\cdot\text{距离}/v$ 。未送 $d$ 和用前缀和 $O(1)$ 得。

2. 数值技巧

所有 $/v$ 的分母相同 → 全程用整数分子累计、最后一次性除 $v$ ，杜绝浮点误差。 $A$ 部分与路线无关直接累加。

3. 滚动数组

转移只依赖区间宽度 $w-1$ 的层，滚动两层即空间 $O(n)$ ；总时间 $O(n^2)$ 。

代码

Python 版：

python

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
50
51
52
53
54
55
56
57
58
59
60
61
62#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 20:00
# update_at: 2026-10-02 20:00

import sys
from bisect import bisect_right
from itertools import accumulate

INF = 10**30  # 不可达哨兵：真实代价上限约 1e18，远小于它


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, v, s = next(data), next(data), next(data)
    cust = [(next(data), next(data), next(data)) for _ in range(n)]  # (p, A, d)
    sum_a = sum(a for _, a, _ in cust)  # A 与路线无关，直接累加

    # 把起点当 d=A=0 的虚拟客户并入，只按位置排序（稳定），虚拟点排在同位置组末尾
    pts = sorted(cust + [(s, 0, 0)], key=lambda e: e[0])
    m = n + 1
    x = [p for p, _, _ in pts]
    d = [dd for _, _, dd in pts]
    pref = list(accumulate(d, initial=0))  # pref[i] = 前 i 个点的 d 之和
    total_d = pref[m]
    si = bisect_right(x, s) - 1  # 虚拟起点下标：最后一个位置为 s 的点

    # 区间 DP：状态 (l, r, 端点) = 已送完连续区间 [l, r]、无人机停在端点。
    # 每次只向外扩展一位，代价 = 扩展前未送客户的 d 和 × 距离 / v（全部 d 在飞行期间同时增长）。
    # 所有除法分母都是同一个 v，故整条路线只在最后除一次 v，途中全用整数分子，避免浮点误差。
    # 转移只依赖宽度 w-1 的层，滚动数组即可，空间 O(n)。
    prev_l = [INF] * (m + 2)
    prev_r = [INF] * (m + 2)
    prev_l[si] = prev_r[si] = 0  # 起点即初始区间，尚未移动，代价为 0
    for w in range(1, m):  # 按区间宽度从小到大推进
        lo, hi = max(0, si - w), min(si, m - 1 - w)  # 保证区间包含 si
        cur_l = [INF] * (m + 2)
        cur_r = [INF] * (m + 2)
        for l in range(lo, hi + 1):
            r = l + w
            if l < si:  # 从 [l+1, r] 向左送第 l 个客户，无人机停在左端
                seg = total_d - (pref[r + 1] - pref[l + 1])  # 扩展前未送名单的 d 和
                cur_l[l] = min(
                    prev_l[l + 1] + seg * abs(x[l + 1] - x[l]),  # 原来停在左端
                    prev_r[l + 1] + seg * abs(x[r] - x[l]),  # 原来停在右端，横穿已送区间
                )
            if r > si:  # 从 [l, r-1] 向右送第 r 个客户，无人机停在右端
                seg = total_d - (pref[r] - pref[l])
                cur_r[l] = min(
                    prev_l[l] + seg * abs(x[l] - x[r]),
                    prev_r[l] + seg * abs(x[r - 1] - x[r]),
                )
        prev_l, prev_r = cur_l, cur_r

    # 全部客户送完 = 区间 [0, m-1]；分子 ÷ v 后向下取整再加常数 A
    print(sum_a + min(prev_l[0], prev_r[0]) // v)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103// main.cpp：区间 DP 求最小生气总量（对应 main.py 的 Python 解法的 C++ 版本）
// 状态 (l, r, end)：已送完排序后连续区间 [l, r]，无人机停在左/右端点。
// 每次向外扩展一位，代价 = 扩展前未送客户 d 之和 × 飞行距离 / v。

/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 02:12
 * update_at: 2026-10-06 02:12
 */

#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;

const int MAXN = 1005;
const ll INF = (ll)4e18;

ll n, v, sx;              // 客户数、无人机速度、起始位置
ll x[MAXN];               // 排序后各点的位置（含虚拟起点）
ll dd[MAXN];              // 排序后各点的 d 值（虚拟起点为 0）
ll pref[MAXN];            // pref[i] = 前 i 个点的 d 之和
ll si;                    // 虚拟起点在排序数组中的下标
ll f[MAXN][2];            // f[l][0/1]：当前层，区间 [l, l+w] 送完、停在左/右端点的最小整数分子
ll g[MAXN][2];            // 上一层（区间宽度 w-1）的 DP 值

int main() {
    scanf("%lld %lld %lld", &n, &v, &sx);
    ll sum_a = 0; // A 部分与路线无关，直接累加
    for (ll i = 1; i <= n; i++) {
        ll p, a, d;
        scanf("%lld %lld %lld", &p, &a, &d);
        x[i] = p;
        dd[i] = d;
        sum_a += a;
    }
    // 把起点当作 d=A=0 的虚拟客户（下标 0），一起按位置排序
    x[0] = sx;
    dd[0] = 0;
    ll m = n + 1; // 总点数（含虚拟起点）
    // 点数 <=1001，用插入排序按位置排好，避免与 DP 下标耦合
    for (ll i = 1; i < m; i++) { // 插入排序
        ll px = x[i], dv = dd[i];
        ll j = i - 1;
        while (j >= 0 && x[j] > px) {
            x[j + 1] = x[j];
            dd[j + 1] = dd[j];
            j--;
        }
        x[j + 1] = px;
        dd[j + 1] = dv;
    }
    // 找虚拟起点下标：最后一个位置 <= s 的点（s 为其中一点）
    si = 0;
    for (ll i = 0; i < m; i++)
        if (x[i] == sx) si = i;

    pref[0] = 0;
    for (ll i = 0; i < m; i++)
        pref[i + 1] = pref[i] + dd[i];
    ll total_d = pref[m]; // 全部客户的 d 之和

    // 滚动数组：g 是宽度 w-1 层，f 是宽度 w 层
    for (ll l = 0; l < m; l++) {
        g[l][0] = INF;
        g[l][1] = INF;
    }
    g[si][0] = 0; // 初始区间 [si, si]，无人机还没动，代价 0
    g[si][1] = 0;

    for (ll w = 1; w < m; w++) {
        ll lo = std::max(0LL, si - w);
        ll hi = std::min(si, m - 1 - w); // 区间 [l, l+w] 必须包含起点 si
        for (ll l = 0; l < m; l++) {
            f[l][0] = INF;
            f[l][1] = INF;
        }
        for (ll l = lo; l <= hi; l++) {
            ll r = l + w;
            // 向左扩展送第 l 个客户：先飞 x[端点] -> x[l]，飞行期间所有未送客户 d 同时增长
            if (l < si) {
                ll seg = total_d - (pref[r + 1] - pref[l + 1]); // 扩展前未送客户的 d 和
                ll c1 = (g[l + 1][0] >= INF) ? INF : g[l + 1][0] + seg * (x[l + 1] - x[l]); // 原停左端
                ll c2 = (g[l + 1][1] >= INF) ? INF : g[l + 1][1] + seg * (x[r] - x[l]);     // 原停右端，横穿区间
                f[l][0] = std::min(c1, c2);
            }
            // 向右扩展送第 r 个客户
            if (r > si) {
                ll seg = total_d - (pref[r] - pref[l]); // 扩展前未送客户的 d 和
                ll c1 = (g[l][0] >= INF) ? INF : g[l][0] + seg * (x[r] - x[l]); // 原停左端，横穿区间
                ll c2 = (g[l][1] >= INF) ? INF : g[l][1] + seg * (x[r] - x[r - 1]); // 原停右端
                f[l][1] = std::min(c1, c2);
            }
        }
        std::swap(f, g); // 滚动：当前层变为下一轮的上一层
    }

    // 全部送完 = 区间 [0, m-1]；分子 ÷ v 后向下取整，再加常数 A
    printf("%lld\n", sum_a + std::min(g[0][0], g[0][1]) / v);
    return 0;
}

复杂度

时间复杂度： $O(n^2)$ 。
空间复杂度： $O(n)$ （滚动）。

总结

「配送顺序 + 等待代价」类问题的标配：位置排序 + 区间 DP 逐位扩展。
「共同分母延迟到最后一除」是精确输出小数类题目的通用防误差技巧。
未送量的前缀和让扩展代价 $O(1)$ ，是 DP 能 $O(n^2)$ 的关键。