以最后一个控制站划分阶段的 DP,把段内花费拆成两个前缀和化为直线截距,用单调队列维护下凸壳把 O(n^2) 转移降到 O(n)。
OJ: roj
题目 ID: 1792
难度:提高+/省选-
标签:动态规划斜率优化单调队列python
创建: 2026-10-08 03:23
更新: 2026-10-08 03:23
形式化题目
牧场自西向东编号
其中
素材说明:本题与 BZOJ 3437「小P的牧场」同源。仓库素材源目录里附带了数据生成脚本 (
data.py),10 组测试数据由该脚本用同一算法的 C++ 参考实现产出, 因此数据规模与题面自洽、但并非官方原题数据;题面本身也可能是网络重建的版本。 本文的解法与main.cpp是独立重写的,10 组数据全部对上(见下文复杂度小节的实测)。
两个关键约束决定了后面的做法:
- 控制站只能向西控制,所以最东边的
号牧场只有自己建站才能被控制, 必有 ,答案是"在 建站"的那一类状态,而不是所有状态的最小值。 ,于是 的前缀和严格递增,这正是后面斜率优化能成立的前提。
正解
思路
阶段怎么划。 一个控制站
瓶颈在哪。 先用前缀和
求和不再是瓶颈了,但每个
于是问题被压缩成一句话:如何在均摊
变量分离。 把 (2) 里与
求最小值的那一项就是"过点
为什么只需要下凸壳 + 单调队列。 两个单调性同时成立:
随 严格递增(横坐标有序,不存在重复横坐标的退化); - 查询斜率
随 严格递增。
第 2 条意味着最优决策点只会向右移动,不需要三分或二分:用一个双端队列维护 决策点的下凸壳,
- 队头弹出:若队头前两个点
满足 , 说明斜率 下 已经不劣于 ,而之后斜率只增不减, 永远不会再被选中; - 队尾弹出:新点
入队前,若队尾两点 与 满足 , 则 落在 的上方(或共线),不可能成为最优决策点,直接弹掉。
设计策点下标为
决策点随
| 入队前队列 | 本次弹掉的队头 | 最优 |
本次弹掉的队尾 | 入队后队列 | ||||
|---|---|---|---|---|---|---|---|---|
| 0 | — | — | — | — | [0] |
0 | 0 | 0 |
| 1 | [0] |
无 | 0 | 无 | [0, 1] |
3 | 5 | |
| 2 | [0, 1] |
0 | 1 | 无 | [1, 2] |
4 | 11 | |
| 3 | [1, 2] |
无 | 1 | 2 | [1, 3] |
8 | 22 | |
| 4 | [1, 3] |
1 | 3 | 无 | [3, 4] |
10 | 34 |
三个阶段各有一条信息值得读出来。
第一,
注意
答案为什么是
样例解释的对照。 样例选
代码
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-08 03:23
# update_at: 2026-10-08 03:23
import sys
def min_cost(cost: list[int], grass: list[int]) -> int:
"""返回在最后一个牧场必建控制站时覆盖全部牧场的最小总花费 f[n]。
转移 f[i] = a_i + i * S1[i] - S2[i] + min_j ( ys[j] - i * xs[j] ),
其中 xs[j] = S1[j](b 的前缀和,因 b_k > 0 而严格递增)、
ys[j] = f[j] + S2[j](S2 是 k * b_k 的前缀和)。
查询斜率 i 严格递增,最优决策点在单调队列维护的下凸壳上单调右移,均摊 O(1)。
"""
n = len(cost) - 1
f = [0] * (n + 1) # f[i]:第 i 个牧场建站,且前 i 个牧场都被控制的最小花费
xs = [0] * (n + 1) # xs[j]:决策点横坐标,即 b 的前缀和 S1[j],严格递增
ys = [0] * (n + 1) # ys[j]:决策点纵坐标,即 f[j] + S2[j]
q = [0] * (n + 1) # 下凸壳上的决策点下标,队头到队尾横坐标递增、相邻斜率递增
head, tail = 0, 1 # 队列区间 [head, tail),初始只有虚拟起点 j = 0
s1 = s2 = 0 # s1 = S1[i],s2 = S2[i],随扫描增量维护
for i in range(1, n + 1):
s1 += grass[i]
s2 += i * grass[i]
# 队头:斜率 i 下若后者已不劣于前者,则前者之后再也不会被选中
while head + 1 < tail:
u, v = q[head], q[head + 1]
still_worse = ys[v] - ys[u] > i * (xs[v] - xs[u])
if still_worse:
break
head += 1
j = q[head]
f[i] = cost[i] + i * s1 - s2 + ys[j] - i * xs[j]
xs[i], ys[i] = s1, f[i] + s2
# 队尾:新点落在队尾两点连线上方(上凸)时,队尾点永不可能最优
while head + 1 < tail:
u, v = q[tail - 2], q[tail - 1]
upper = (ys[v] - ys[u]) * (xs[i] - xs[v]) >= (ys[i] - ys[v]) * (xs[v] - xs[u])
if not upper:
break
tail -= 1
q[tail] = i
tail += 1
return f[n] # 最东边的牧场只能自建站才被覆盖,故答案就是 f[n]
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data) # 牧场数目
cost = [0] + [next(data) for _ in range(n)] # cost[i] = a_i,建站花费
grass = [0] + [next(data) for _ in range(n)] # grass[i] = b_i,放养量
print(min_cost(cost, grass))
if __name__ == "__main__":
solve()C++ 版:
/**
* 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-08 03:23
* update_at: 2026-10-08 03:23
*/
// ROJ 1792 小P的牧场:斜率优化 DP(单调队列维护下凸壳),O(n)。
//
// 模型:选出递增的位置序列 0 = p0 < p1 < ... < pm = n(pm = n 才能控制最东边),
// 总花费 = sum_t ( a[p_t] + sum_{k=p_{t-1}+1}^{p_t-1} (p_t - k) * b_k )。
// DP:f[i] 表示第 i 个牧场必建控制站、且前 i 个牧场都被控制时的最小花费,
// f[i] = a_i + min_{0 <= j < i} { f[j] + sum_{k=j+1}^{i-1} (i - k) * b_k }
// = a_i + i * S1[i] - S2[i] + min_{0 <= j < i} { Y[j] - i * X[j] },
// 其中 S1[i] = sum_{k<=i} b_k,S2[i] = sum_{k<=i} k * b_k,
// X[j] = S1[j](严格递增),Y[j] = f[j] + S2[j]。
// 查询斜率 i 严格递增 + 横坐标 X 严格递增 => 决策点在单调队列维护的下凸壳上单调右移。
#include <cstdio>
using namespace std;
typedef long long ll;
const int MAXN = 1000005;
ll n; // 牧场数目
ll a[MAXN]; // a[i]:在第 i 个牧场建控制站的花费
ll S1[MAXN]; // S1[i] = sum_{k<=i} b_k
ll S2[MAXN]; // S2[i] = sum_{k<=i} k * b_k
ll f[MAXN]; // f[i]:第 i 个牧场必建控制站、前 i 个牧场均被控制的最小总花费
ll que[MAXN]; // 单调队列(存决策点下标),维护决策点的下凸壳
ll head, tail; // 队列区间 [head, tail)
// 快速读入:题面数字均为非负整数,n 最大 10^6,读入量约 10 MB
ll readInt() {
int c = getchar();
while (c < '0' || c > '9') c = getchar();
ll x = 0;
while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = getchar(); }
return x;
}
// 决策点 j 的坐标:横坐标 X[j] = S1[j],纵坐标 Y[j] = f[j] + S2[j]
ll X(ll j) { return S1[j]; }
ll Y(ll j) { return f[j] + S2[j]; }
// 下凸壳维护:若 slope(j,k) >= slope(k,m),则 k 落在 jm 上方或线上,永远不优,可弹掉。
// 叉积最大约 10^16 * 10^10 = 10^26,远超 long long(约 9.2 * 10^18),中间量必须声明为 __int128。
bool bad(ll j, ll k, ll m) {
__int128 dy1 = Y(k) - Y(j), dx1 = X(k) - X(j);
__int128 dy2 = Y(m) - Y(k), dx2 = X(m) - X(k);
return dy1 * dx2 >= dy2 * dx1;
}
// 队头决策:斜率 i 下若 k 已经不比 j 差,则 j 之后再也不会更优
bool front_worse(ll j, ll k, ll i) {
return Y(k) - Y(j) <= i * (X(k) - X(j));
}
int main() {
n = readInt();
for (ll i = 1; i <= n; ++i) a[i] = readInt();
for (ll i = 1; i <= n; ++i) {
ll b = readInt();
S1[i] = S1[i - 1] + b;
S2[i] = S2[i - 1] + b * i;
}
head = 0;
tail = 0;
que[tail++] = 0; // 虚拟起点 j = 0:西边没有控制站,f[0] = S1[0] = S2[0] = 0
for (ll i = 1; i <= n; ++i) {
while (head + 1 < tail && front_worse(que[head], que[head + 1], i)) ++head;
ll j = que[head]; // 队头即当前 i 的最优决策点
f[i] = a[i] + i * S1[i] - S2[i] + Y(j) - i * X(j);
while (head + 1 < tail && bad(que[tail - 2], que[tail - 1], i)) --tail;
que[tail++] = i;
}
// 最东边的牧场必须建站才可能被控制,故答案就是 f[n],不需要对 f 取最小值
printf("%lld\n", f[n]);
return 0;
}复杂度
- 时间:前缀和与 DP 各一遍扫描,每个决策点最多入队一次、出队一次,
转移均摊
,总时间 。 - 空间:
各一个长度 的 long long数组,加一个的队列, 。 时约 40 MB,低于 256 MB 限制。 - 溢出边界:
, 在 量级,必须全程 64 位。链式相乘的叉积最坏可以达到 ,已经越过 long long的,所以 main.cpp的bad()把中间量声明为__int128作为保险。 (实测:把__int128换回long long后素材源的 10 组数据仍然全对, 说明该点的链上叉积尚未真的溢出——但它是坏数据下的确定性风险,保留__int128。 Python 版整数无上限,天然安全。) - 与 C++ 版的关系:Python 版是同一算法的直接落地——前缀和增量维护、
队列用预分配
list+ 头尾指针模拟,不依赖第三方库;每步只做常数次大整数运算,时大约需要数秒,可能吃满 1.5 s 的时限,这是 Python 语言常数的问题, 不是算法降级。 - 实测:
main.cpp用-O2编译后跑素材源的 10 组数据全部 PASS, 最大规模的n = 10^6点分别耗时 0.14–0.20 s、峰值内存约 40 MB(限制 1.5 s / 256 MB);main.py同样 10 组全部逐字节对上,单点耗时 0.4–0.6 s。 此外拿的 400 组固定种子随机数据与 朴素 DP 对照,两版均无失配。
总结
- 先让转移可读,再让转移变快:先把内层求和用两个前缀和压成
, 式子里才浮出"斜率 横坐标 + 常数"的形状,变量分离是斜率优化的入场券。 - 两个单调性一个都不能少:横坐标
严格递增来自 ; 查询斜率 严格递增来自"按牧场编号推进"。前者保证下凸壳无重复横坐标, 后者让队头弹出合法、让最优决策点单调右移。 - 队头与队尾维护的是两件不同的事:队头弹的是"对当前及以后斜率都不再优"的点, 队尾弹的是"破坏下凸性"的点,写反或合并都会错。
- 判定用叉积不用除法:避免浮点误差;而叉积在坏数据下会越出
long long, 所以 C++ 里把中间量声明为__int128,这是零成本的安全边。 - 答案是
而不是 :因为最东边的牧场只能由自己建站来覆盖。
图示解析
下图直接用样例的 5 个决策点画出这件事。每个点是
Y = f[j] + S_kb[j] ← 每个点旁边标出“点坐标 与 它和前一个保留下来的点的斜率”
34 | ● j=4 (10,34)
| slope 6.00 /
22 | ● j=3 (8,22)
| slope 2.75 /
11 | ✗ j=2 (4,11) ← 被队尾弹掉,在 j=1—j=3 连线上方
| /
| / slope 6.00(j=2 存在时的斜率,下降趋势→破坏下凸性)
5 | ● j=1 (3,5)
| slope 1.67 /
0 | ● j=0 (0,0)
+-------------------------------------------------------------------→ X = S_b[j]
0 3 4 8 10读图要点有三处。
第一,斜率单调递增就是下凸壳:保留下来的相邻斜率按
第二,查询斜率
第三,横坐标严格递增自动成立: