形式化题目

数轴上有 $n$ 个客户，第 $i$ 个客户位于坐标 $p_i$，生气值为 $A_i$。人初始站在第 $c$ 个客户的坐标处，每单位时间沿数轴移动 1 个单位距离，可以随时向左或向右走。客户 $i$ 在时刻 $t$ 被送达时产生 $t \times A_i$ 的生气量。要求访问全部 $n$ 个客户各一次，求送完之后生气总量之和的最小值。

样例 $n = 5$、$c = 3$，位置与生气值为 $(2,10),\ (3,20),\ (5,20),\ (6,30),\ (8,10)$，输出 $270$。一条最优路线是从位置 5 出发、依次走向 6、3、2、8，逐段计费过程如下表。

这张表说明了题目的计费方式：每个客户的生气量只取决于它被送达的时刻，而时刻等于此前累计走过的路程长度；路线每多走一步，所有还没送达的客户都在按各自的 $A$ 持续生气。注意最优路线里先向右送到 6 又折返向左，所以"永远送最近的"这类贪心并不成立。

正解

思路

朴素做法与瓶颈。 最直接的思路是枚举 $n$ 个客户的全排列，按该顺序走过去并累加"累计路程 $\times$ 生气值"，但阶乘级的路线数量在 $n = 50$ 时完全不可行。贪心也不成立：先送"生气值最大但最远"的客户，会让路上所有客户长时间等待；先送最近的，又无视生气值的权重——两种贪心都能构造出反例。这说明必须记录"已经送了哪些人"才能决策，问题的关键是把这个状态压小。

观察一：第一次经过就送达。 如果某条路线经过某个客户的坐标却没有立刻送达，把它改成立刻送达：路线的几何形状完全不变，因此每个客户被送达时走过的总路程只会缩短或不变，而 $A \geqslant 0$，总生气量不增。于是总存在一条最优路线，客户在第一次被路过时就被送达，"路过却不送"的决策可以整体删掉。

观察二：已送达集是包含起点的连续区间。 由观察一，任意时刻已送达的客户恰好是"从起点到当前位置这段扫掠区间 $[L, R]$ 覆盖到的客户"——扫过的每个坐标上的客户都已经送掉了。所以"送了哪些人"这个本有 $2^n$ 种可能的子集状态，实际只会取到 $O(n^2)$ 个按位置连续、且包含起点的区间。

观察三:人站在扫掠区间的一个端点。 只要还有客户没送,而人却在区间内部(既不在 $L$ 也不在 $R$),说明他刚从端点折返回来:这一步没有送达任何新客户(区间没有扩张),却让区间外所有等待的客户多生气了“距离 $\times$ 未送达生气值之和”。把这段折返从路线里删掉、后续照原样走，代价不会变差（剩余客户生气值全为 0 时相等）。因此只需考虑"人站在当前区间左端或右端"的状态;全部送完之后人停在哪一端都不再产生费用。

状态与转移。 先把客户按坐标升序排序（题面不保证输入有序），记 $s$ 为起点客户排序后的下标。定义

要得到“区间 $[l, r]$、人在左端”，上一步必然是区间 $[l+1, r]$（刚把最左端 $l$ 送达），且人在 $l+1$ 或在 $r$：送达集只增不减，少掉的恰好只能是最左端；至于在已送达区间内部空走到另一端，它不送达任何新客户、只会增加非负代价，由观察三直接排除。“人在右端”对称地来自 $[l, r-1]$：

其中 $W(a, b)$ 表示区间 $[a, b]$ 之外的客户生气值之和。它的含义是：从"已送达 $[a,b]$"的状态出发走 $d$ 距离，期间只有区间外的客户还在生气，代价恰好是 $d \times W(a,b)$；用前缀和 $S$ 可以 $O(1)$ 求出 $W(a,b) = \text{sum}(A) - (S_{b+1} - S_{a})$。

基态为 $f[s][s][0] = f[s][s][1] = 0$（起点客户在时刻 0 送达，还没产生生气量），其余初始化为无穷大——不包含起点的区间永远推不出来，自然保持无穷。按区间长度从小到大递推，因为 $f[l][r]$ 只依赖少一个端点的更短区间；答案是 $\min\big(f[0][n-1][0],\ f[0][n-1][1]\big)$。

样例 DP 表

下面把样例的区间 DP 表完整列出（行是 $l$、列是 $r$，单元格是 $f[l][r][0] / f[l][r][1]$，即"已送达 $[l,r]$、人在左端 / 人在右端"的两个值；· 表示 $l > r$ 不构成区间，— 表示该区间不含起点、不可达）。

读这张表要抓三点。第一，起点是第 3 个客户、排序后下标 $s = 2$，所以只有 $l \leqslant 2 \leqslant r$ 的区间才可能可达，表里成片的 — 正是"送达集必须是含起点的连续区间"这条不变量的体现。第二，挑一格看转移：$f[1][3][0] = 190$ 表示已送达位置 $\{3,5,6\}$、人站在 3，它来自 $f[2][3][1] = 70$（已送达 $\{5,6\}$、人在 6）横穿回到 3——距离 $6-3=3$，路上还没送达的是位置 2、3、8 三个客户（含正要送达的位置 3），生气值之和 $10+20+10=40$，于是 $70 + 3 \times 40 = 190$。第三，右下角 $\min(310, 270) = 270$ 就是答案，其来源链 $f[2][2] \to f[2][3] \to f[1][3] \to f[0][3] \to f[0][4]$ 正对应前面样例表里的路线 5 → 6 → 3 → 2 → 8。

与代码对应。 solve 只做读入与输出：order 按坐标升序排序并保留原下标、s = order.index(c - 1) 定位起点，然后调用 min_anger。min_anger 承载全部算法：S 是生气值前缀和；两个等待代价 wait_from_right = total - (S[r+1] - S[l+1]) 与 wait_from_left = total - (S[r] - S[l]) 就是上文的 $W(l{+}1,r)$ 与 $W(l,r{-}1)$；双层 for 按区间长度递增填表，return min(f[0][n - 1]) 正是答案位置。

代码

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
63#!/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 19:55
# update_at: 2026-10-02 20:05

import sys

INF = 10**15  # "还够不着"的不可达哨兵，远大于任何合法生气总量


def min_anger(pos: list[int], anger: list[int], s: int) -> int:
    """区间 DP：客户按坐标升序、起点为下标 s，返回送完全部客户的最小生气总量。"""
    n = len(pos)

    # 前缀和：S[r+1]-S[l] = 区间 [l,r] 已送达客户的生气值之和
    S = [0]
    for a in anger:
        S.append(S[-1] + a)
    total = S[n]

    # f[l][r][0/1]：已送达连续区间 [l,r]、人停在左端 l(0) / 右端 r(1)，
    # 此时已发生的生气总量最小值。未送达客户在这段时间里一直按 t*A 累加。
    f = [[[INF, INF] for _ in range(n)] for _ in range(n)]
    f[s][s][0] = f[s][s][1] = 0

    for length in range(2, n + 1):
        for l in range(n - length + 1):
            r = l + length - 1
            # 走路期间仍在生气的是"区间外 + 正要收进来的那端"：
            # 由 [l+1,r] 走向 l：剩下 {0..l} 与 {r+1..n-1}
            wait_from_right = total - (S[r + 1] - S[l + 1])
            # 由 [l,r-1] 走向 r：剩下 {0..l-1} 与 {r..n-1}
            wait_from_left = total - (S[r] - S[l])

            f[l][r][0] = min(
                f[l + 1][r][0] + (pos[l + 1] - pos[l]) * wait_from_right,  # 左邻直走
                f[l + 1][r][1] + (pos[r] - pos[l]) * wait_from_right,       # 从右端折返
            )
            f[l][r][1] = min(
                f[l][r - 1][0] + (pos[r] - pos[l]) * wait_from_left,        # 从左端横穿
                f[l][r - 1][1] + (pos[r] - pos[r - 1]) * wait_from_left,    # 右邻直走
            )

    return min(f[0][n - 1])


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, c = next(data), next(data)
    raw = [(next(data), next(data)) for _ in range(n)]  # (位置 p, 生气值 A)

    order = sorted(range(n), key=raw.__getitem__)  # 按位置升序，区间 DP 依赖有序
    s = order.index(c - 1)                         # 起点客户排序后落在哪个下标
    pos = [raw[i][0] for i in order]
    anger = [raw[i][1] for i in order]

    print(min_anger(pos, anger, s))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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:11
 * update_at: 2026-10-06 02:11
 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 55;
const ll INF = 1000000000000000000LL; // "还够不着"的不可达哨兵，远大于任何合法生气总量

struct Customer {
    ll p;   // 位置
    ll a;   // 生气值
    int id; // 原始输入下标（0 起），用来在排序后定位起点
};
Customer cust[MAXN];

int n;         // 客户数量
int c;         // 阿什尼初始在第 c 个客户的位置（1 起）
ll pos[MAXN];  // pos[i] 排序后第 i 个客户的位置
ll sumA[MAXN]; // sumA[i+1]-sumA[j] = 排序后区间 [j,i] 的生气值之和（前缀和）
ll total;      // 全部客户的生气值之和

// f[l][r][0/1]：已送达连续区间 [l,r]、人停在左端 l(0) 或右端 r(1) 时，
// 已发生的生气总量最小值。区间外未送达客户在这段移动中一直按各自的 A 累加。
ll f[MAXN][MAXN][2];

// 客户按位置升序，区间 DP 才能把"已送达集"表示成连续下标区间
bool cmp_pos(Customer x, Customer y) {
    return x.p < y.p;
}

int main() {
    scanf("%d %d", &n, &c);
    for (int i = 0; i < n; i++) {
        scanf("%lld %lld", &cust[i].p, &cust[i].a);
        cust[i].id = i;
    }
    int start_id = c - 1; // 起点客户的原始下标

    sort(cust, cust + n, cmp_pos);

    int s = 0; // 起点客户排序后落在哪个下标
    for (int i = 0; i < n; i++) {
        pos[i] = cust[i].p;
        if (cust[i].id == start_id) {
            s = i;
        }
    }
    sumA[0] = 0;
    for (int i = 0; i < n; i++) {
        sumA[i + 1] = sumA[i] + cust[i].a;
    }
    total = sumA[n];

    for (int l = 0; l < n; l++) {
        for (int r = 0; r < n; r++) {
            f[l][r][0] = INF;
            f[l][r][1] = INF;
        }
    }
    f[s][s][0] = 0;
    f[s][s][1] = 0;

    for (int len = 2; len <= n; len++) {
        for (int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            // W(l+1,r)：由 [l+1,r] 走向 l 时，区间外仍在生气的客户生气值之和
            ll wait_from_right = total - (sumA[r + 1] - sumA[l + 1]);
            // W(l,r-1)：由 [l,r-1] 走向 r 时，区间外仍在生气的客户生气值之和
            ll wait_from_left = total - (sumA[r] - sumA[l]);

            ll v0 = f[l + 1][r][0] + (pos[l + 1] - pos[l]) * wait_from_right; // 从 l+1 直走到 l
            ll v1 = f[l + 1][r][1] + (pos[r] - pos[l]) * wait_from_right;     // 从右端 r 折返到 l
            if (v1 < v0) {
                v0 = v1;
            }
            f[l][r][0] = v0;

            ll v2 = f[l][r - 1][0] + (pos[r] - pos[l]) * wait_from_left;      // 从左端 l 横穿到 r
            ll v3 = f[l][r - 1][1] + (pos[r] - pos[r - 1]) * wait_from_left;  // 从 r-1 直走到 r
            if (v3 < v2) {
                v2 = v3;
            }
            f[l][r][1] = v2;
        }
    }

    ll answer = f[0][n - 1][0];
    if (f[0][n - 1][1] < answer) {
        answer = f[0][n - 1][1];
    }
    printf("%lld\n", answer);
    return 0;
}

复杂度

• 时间复杂度：排序 $O(n \log n)$，DP 共 $O(n^2)$ 个状态、每状态 $O(1)$ 次转移，总计 $O(n^2)$。一般区间 DP 内层要枚举切分点，本题的转移只"扩一个端点"，因此是 $O(n^2)$ 而不是 $O(n^3)$，与参考 C++ 实现同阶；$n \leqslant 50$ 时只有约 2500 个状态，实测 10 组真实数据单组约 0.02 s，远小于 1000 ms 限时。
• 空间复杂度：$O(n^2)$，DP 表 $n \times n \times 2$ 加长度 $n+1$ 的前缀和，远小于 128 MB 内存限制。

总结

• 本题的核心是把"任意送货路线"翻译成连续区间：第一次经过即送达（观察一）→ 已送达集是含起点的连续区间（观察二）→ 区间内折返是纯浪费、人只站在端点（观察三），三步把阶乘级的路线压缩成 $O(n^2)$ 个状态。
• 生气量随时间线性增长，所以一段移动的代价可以拆成"距离 $\times$ 未送达生气值之和"，配前缀和 $O(1)$ 查询，这正是转移里 $W(a,b)$ 的来源。
• 区间 DP 按长度递增填表，状态只依赖更短区间，无穷大哨兵天然排除"不含起点"的非法区间，答案落在 $f[0][n-1][*]$。
• $n \leqslant 50$ 提示的是"状态数必须从指数降到多项式"，而不是"数据小可以直接暴力"。

图示解析

这张图串起本题从观察到答案的主线：

1
2
3
4
5数轴送货路线，n <= 50 枚举全排列不可行
|- 观察一/二：第一次经过就送达 → 已送达集是含起点的连续区间 [l, r]
|  `- 观察三：区间内折返不送人是纯浪费 → 人只站在区间端点
|     `- 区间 DP：f[l][r][0/1]，走路代价 = 距离 × 未送达生气值之和
|        `- 按区间长度递推，答案 min(f[0][n-1][0], f[0][n-1][1])

先看每层节点的含义：前两层是把路线自由度砍掉的关键观察，第三层把观察落成状态与代价公式，最后一层是填表顺序和答案位置。顺着箭头检查可以发现，每一层都只用到上一层的结论，没有任何跳步；具体数值的验证则交给正文里的样例 DP 表。