外卖路线的取舍决策最大净赚：区间记忆化搜索 best(l,r,side,passed)，每步决定当前端客户送/放弃并走向下一端，移动成本随未决客户数增长，O(n^2)。
OJ: roj
题目 ID: 20014
难度:省选/NOI-
标签:DP区间DP记忆化搜索
创建: 2026-10-02 20:35
更新: 2026-10-07 13:50
形式化题目
客户在位置
正解
思路
1. 区间决策的对称性
决策顺序中，未决客户在位置轴上构成连续区间
passed = 已走过但区间外的未决客户数（成本乘数）。
2. 四分支转移
在 side 端的客户二选一（送/放弃），然后走向相邻端或掉头到远端：
- 送：
、 passed+1； - 放弃：
passed不变； - 移动成本
距离 当前 passed（决策前的未决数，按题面）。
@cache 记忆化，状态
3. 实现要点
- 位置先排序（含原点虚拟客户口径按题面）；
- 掉头分支的移动距离用「远端位置」计算；
- 记忆化 + 递归深度
，Python 可承受（ @cache）。
代码
Python 版：
python
#!/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:11
# update_at: 2026-10-02 20:11
import sys
from functools import cache
POS: list[int] = [] # 客户位置，升序（位置可负、互不为 0）
EARN: list[int] = [] # EARN[i] 是位置 POS[i] 处外卖的价格 e
@cache
def best(l: int, r: int, side: int, passed: int) -> int:
"""还没决定去留的客户恰为区间 [l, r]，无人机停在 side 端，
区间外已走过 passed 个"未决定"客户时的最大净赚。"""
if l == r: # 最后一个未决定客户：要么现在送，要么永远放弃
x = POS[l]
return max(EARN[l] - abs(x) * (passed + 1), -abs(x) * passed)
if side == 0: # 在左端，决定最左客户 l 的去留
x, nxt, far = POS[l], POS[l + 1], POS[r]
return max(
EARN[l] + best(l + 1, r, 0, passed + 1) - (nxt - x) * (passed + 1), # 送，继续向左
EARN[l] + best(l + 1, r, 1, passed + 1) - (far - x) * (passed + 1), # 送，掉头向右
best(l + 1, r, 0, passed) - (nxt - x) * passed, # 放弃，继续向左
best(l + 1, r, 1, passed) - (far - x) * passed, # 放弃，掉头向右
)
x, prv, far = POS[r], POS[r - 1], POS[l] # 在右端，决定最右客户 r 的去留
return max(
EARN[r] + best(l, r - 1, 1, passed + 1) - (x - prv) * (passed + 1), # 送，继续向右
EARN[r] + best(l, r - 1, 0, passed + 1) - (x - far) * (passed + 1), # 送，掉头向左
best(l, r - 1, 1, passed) - (x - prv) * passed, # 放弃，继续向右
best(l, r - 1, 0, passed) - (x - far) * passed, # 放弃，掉头向左
)
def solve() -> None:
global POS, EARN
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
pos = [next(data) for _ in range(n)] # 客户位置（可负、可乱序）
earn = [next(data) for _ in range(n)] # 对应客户的外卖价格
pairs = sorted(zip(pos, earn)) # 按位置排序，区间 DP 才能从两端逐个决定
POS = [x for x, _ in pairs]
EARN = [v for _, v in pairs]
print(max(best(0, n - 1, 0, 0), best(0, n - 1, 1, 0)))
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* 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:18
* update_at: 2026-10-06 02:18
*/
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 105; // n <= 100，passed 最多取到 n
pair<ll, ll> customer[MAXN]; // customer[i] = (客户位置, 外卖价格)，读入后按位置升序
ll pos[MAXN]; // pos[i] 第 i 个客户的位置（升序，可负）
ll earn[MAXN]; // earn[i] 第 i 个客户的外卖价格 e
// memo[l][r][side][passed] 存对应状态的最大净赚；vis 标记该状态是否已算过
ll memo[MAXN][MAXN][2][MAXN];
char vis[MAXN][MAXN][2][MAXN];
// 取绝对值，避免使用强制转换
ll abs_ll(ll v) {
if (v < 0) return -v;
return v;
}
// best(l, r, side, passed)：
// 还没决定去留的客户恰为区间 [l, r]（pos 升序），无人机停在区间端点；
// side = 0 表示停在左端 l，side = 1 表示停在右端 r；
// passed = 已经送过外卖的客户数，作为移动成本的乘数。
// 返回从该状态继续决策能得到的最大净赚。
ll best(ll l, ll r, ll side, ll passed) {
if (vis[l][r][side][passed]) return memo[l][r][side][passed];
vis[l][r][side][passed] = 1;
ll res;
if (l == r) {
// 只剩最后一个未决定客户：要么现在送，要么永远放弃
ll d = abs_ll(pos[l]);
ll send = earn[l] - d * (passed + 1); // 送：得到 e_i，付出时间成本
ll giveup = -d * passed; // 放弃：只付移动成本
res = send > giveup ? send : giveup;
} else if (side == 0) {
// 在左端，决定最左客户 l 的去留，之后停在 l+1 或掉头到右端 r
ll x = pos[l], nxt = pos[l + 1], far = pos[r];
ll go_left = nxt - x; // 继续向左走的距离
ll go_far = far - x; // 掉头走到右端的距离
ll best_val;
// 送 l，继续向左
best_val = earn[l] + best(l + 1, r, 0, passed + 1) - go_left * (passed + 1);
// 送 l，掉头向右
ll cand = earn[l] + best(l + 1, r, 1, passed + 1) - go_far * (passed + 1);
if (cand > best_val) best_val = cand;
// 放弃 l，继续向左
cand = best(l + 1, r, 0, passed) - go_left * passed;
if (cand > best_val) best_val = cand;
// 放弃 l，掉头向右
cand = best(l + 1, r, 1, passed) - go_far * passed;
if (cand > best_val) best_val = cand;
res = best_val;
} else {
// 在右端，决定最右客户 r 的去留，之后停在 r-1 或掉头到左端 l
ll x = pos[r], prv = pos[r - 1], far = pos[l];
ll go_right = x - prv; // 继续向右走的距离
ll go_far = x - far; // 掉头走到左端的距离
ll best_val;
// 送 r，继续向右
best_val = earn[r] + best(l, r - 1, 1, passed + 1) - go_right * (passed + 1);
// 送 r，掉头向左
ll cand = earn[r] + best(l, r - 1, 0, passed + 1) - go_far * (passed + 1);
if (cand > best_val) best_val = cand;
// 放弃 r，继续向右
cand = best(l, r - 1, 1, passed) - go_right * passed;
if (cand > best_val) best_val = cand;
// 放弃 r，掉头向左
cand = best(l, r - 1, 0, passed) - go_far * passed;
if (cand > best_val) best_val = cand;
res = best_val;
}
memo[l][r][side][passed] = res;
return res;
}
int main() {
ll n;
scanf("%lld", &n);
for (int i = 0; i < n; i++) scanf("%lld", &customer[i].first);
for (int i = 0; i < n; i++) scanf("%lld", &customer[i].second);
// 按位置排序，区间 DP 才能从两端逐个决定客户的去留
sort(customer, customer + n);
for (int i = 0; i < n; i++) {
pos[i] = customer[i].first;
earn[i] = customer[i].second;
}
ll ans_left = best(0, n - 1, 0, 0);
ll ans_right = best(0, n - 1, 1, 0);
printf("%lld\n", ans_left > ans_right ? ans_left : ans_right);
return 0;
}复杂度
- 时间复杂度：
。 - 空间复杂度：
（记忆化缓存）。
总结
- 「边走边决策 + 时间成本」的最大收益 = 区间 DP 记忆化，状态带「已过未决数」乘数。
- 送/放弃 × 继续/掉头的四分支是这类「区间端点决策」的模板。
- 移动成本乘数建模为
passed，让转移保持。