小P的牧场

GitHub跳转原题关系图返回列表

以最后一个控制站划分阶段的 DP,把段内花费拆成两个前缀和化为直线截距,用单调队列维护下凸壳把 O(n^2) 转移降到 O(n)。

OJ: roj

题目 ID: 1792

难度:提高+/省选-

标签:动态规划斜率优化单调队列python

创建: 2026-10-08 03:23

更新: 2026-10-08 03:23

形式化题目

牧场自西向东编号 1…n1 \dots n。选出若干个建站位置,构成递增序列

0=p0<p1<p2<⋯<pm=n,0 = p_0 < p_1 < p_2 < \dots < p_m = n,

其中 p0=0p_0 = 0 是一个虚拟起点(表示"西边没有更早的控制站")。区间 [pt−1+1, pt−1][p_{t-1}+1,\, p_t-1] 里的每个牧场 kk 都由控制站 ptp_t 控制,控制花费为 (pt−k)⋅bk(p_t - k) \cdot b_k(距离不含 kk 自身、含控制站所在牧场 ptp_t, 所以 k=ptk = p_t 时距离为 00);牧场 ptp_t 自身另付建站费 apta_{p_t}。 求

min⁡∑t=1m(apt+∑k=pt−1+1pt−1(pt−k) bk).\min \sum_{t=1}^{m} \left( a_{p_t} + \sum_{k=p_{t-1}+1}^{p_t-1} (p_t - k)\, b_k \right).

素材说明:本题与 BZOJ 3437「小P的牧场」同源。仓库素材源目录里附带了数据生成脚本 (data.py),10 组测试数据由该脚本用同一算法的 C++ 参考实现产出, 因此数据规模与题面自洽、但并非官方原题数据;题面本身也可能是网络重建的版本。 本文的解法与 main.cpp 是独立重写的,10 组数据全部对上(见下文复杂度小节的实测)。

两个关键约束决定了后面的做法:

  • 控制站只能向西控制,所以最东边的 nn 号牧场只有自己建站才能被控制, 必有 pm=np_m = n,答案是"在 nn 建站"的那一类状态,而不是所有状态的最小值。
  • ai,bi>0a_i, b_i > 0,于是 bb 的前缀和严格递增,这正是后面斜率优化能成立的前提。

正解

思路

阶段怎么划。 一个控制站 jj 只能管到西边第一个控制站之前,所以"上一个控制站的位置" 就是唯一需要记住的历史信息。设 f[i]f[i] 为"第 ii 个牧场必建控制站、且前 ii 个牧场 全都被控制"的最小总花费,枚举上一个控制站 jj(j=0j = 0 表示西边没有控制站):

f[i]=ai+min⁡0⩽j<i{f[j]+∑k=j+1i−1(i−k) bk}.(1)f[i] = a_i + \min_{0 \leqslant j < i} \left\{ f[j] + \sum_{k=j+1}^{i-1} (i - k)\, b_k \right\}. \tag{1}

瓶颈在哪。 先用前缀和 Sb[x]=∑k⩽xbkS_b[x] = \sum_{k \leqslant x} b_k、Skb[x]=∑k⩽xk bkS_{kb}[x] = \sum_{k \leqslant x} k\,b_k 把内层求和算成 O(1)O(1),式子变成

f[i]=ai+i Sb[i−1]−Skb[i−1]+min⁡0⩽j<i{f[j]−i Sb[j]+Skb[j]}.(2)f[i] = a_i + i\,S_b[i - 1] - S_{kb}[i - 1] + \min_{0 \leqslant j < i} \left\{ f[j] - i\,S_b[j] + S_{kb}[j] \right\}. \tag{2}

求和不再是瓶颈了,但每个 ii 仍要遍历全部 jj:状态 O(n)O(n)、单次转移 O(n)O(n), 总体 O(n2)O(n^2)。n=106n = 10^6 时是 101210^{12} 量级,只有 n⩽1000n \leqslant 1000 的子任务能过。

于是问题被压缩成一句话:如何在均摊 O(1)O(1) 内求出 min⁡j{f[j]−i Sb[j]+Skb[j]}\min_j \{ f[j] - i\,S_b[j] + S_{kb}[j] \}。

变量分离。 把 (2) 里与 jj 有关的量挪到一边、与 ii 有关的量挪到另一边,令

X[j]=Sb[j],Y[j]=f[j]+Skb[j].X[j] = S_b[j], \qquad Y[j] = f[j] + S_{kb}[j].

X[j]X[j] 只由 jj 决定,Y[j]Y[j] 只由 jj 决定,而 ii 只出现在斜率位置:

f[i]=ai+i Sb[i−1]−Skb[i−1]+min⁡0⩽j<i(Y[j]−i⋅X[j]).f[i] = a_i + i\,S_b[i-1] - S_{kb}[i-1] + \min_{0 \leqslant j < i} \bigl( Y[j] - i \cdot X[j] \bigr).

求最小值的那一项就是"过点 (X[j],Y[j])(X[j], Y[j])、斜率为 ii 的直线在 yy 轴上的截距"的相反数: 移项得 Y[j]=i⋅X[j]+CY[j] = i \cdot X[j] + C,CC 越小则 f[i]f[i] 越小。枚举 jj 变成了在平面上 挑一个点,这是斜率优化的标准入口。

为什么只需要下凸壳 + 单调队列。 两个单调性同时成立:

  1. bk>0⇒X[j]=Sb[j]b_k > 0 \Rightarrow X[j] = S_b[j] 随 jj 严格递增(横坐标有序,不存在重复横坐标的退化);
  2. 查询斜率 K=iK = i 随 ii 严格递增。

第 2 条意味着最优决策点只会向右移动,不需要三分或二分:用一个双端队列维护 决策点的下凸壳,

  • 队头弹出:若队头前两个点 u,vu, v 满足 Y[v]−Y[u]X[v]−X[u]⩽i\dfrac{Y[v] - Y[u]}{X[v] - X[u]} \leqslant i, 说明斜率 ii 下 vv 已经不劣于 uu,而之后斜率只增不减,uu 永远不会再被选中;
  • 队尾弹出:新点 ii 入队前,若队尾两点 u,vu, v 与 ii 满足 Y[v]−Y[u]X[v]−X[u]⩾Y[i]−Y[v]X[i]−X[v]\dfrac{Y[v]-Y[u]}{X[v]-X[u]} \geqslant \dfrac{Y[i]-Y[v]}{X[i]-X[v]}, 则 vv 落在 uiui 的上方(或共线),不可能成为最优决策点,直接弹掉。

设计策点下标为 j1<j2<⋯<jkj_1 < j_2 < \dots < j_k,则下凸壳等价于相邻斜率 Y[jt+1]−Y[jt]X[jt+1]−X[jt]\dfrac{Y[j_{t+1}] - Y[j_t]}{X[j_{t+1}] - X[j_t]} 严格递增。 入队时把末尾违反递增的斜率对应的点弹掉,就维护住了这个不变量。

决策点随 ii 右移的过程。 用小数据 n=4n = 4、a=(2,4,2,4)a = (2,4,2,4)、b=(3,1,4,2)b = (3,1,4,2) (样例,答案 99)追踪一遍。前缀和为 Sb=(0,3,4,8,10)S_b = (0,3,4,8,10)、 Skb=(0,3,5,17,25)S_{kb} = (0,3,5,17,25)。每列给出当前队列、队头被弹掉的点、以及算出的 f[i]f[i]:

ii 入队前队列 本次弹掉的队头 最优 jj 本次弹掉的队尾 入队后队列 X[i]=Sb[i]X[i] = S_b[i] Y[i]=f[i]+Skb[i]Y[i] = f[i] + S_{kb}[i] f[i]f[i]
0 — — — — [0] 0 0 0
1 [0] 无 0 无 [0, 1] 3 5 2+3−3+0=22+3-3+0=2
2 [0, 1] 0 1 无 [1, 2] 4 11 4+6−3+(5−3⋅3)=64+6-3+(5-3\cdot3)=6
3 [1, 2] 无 1 2 [1, 3] 8 22 2+12−5+(5−3⋅3)=52+12-5+(5-3\cdot3)=5
4 [1, 3] 1 3 无 [3, 4] 10 34 4+40−25+(22−4⋅8)=94+40-25+(22-4\cdot8)=9

三个阶段各有一条信息值得读出来。

第一,i=2i = 2 时队头弹出的是 j=0j = 0:点 (0,0)(0,0) 与 (Sb[1],Y[1])=(3,5)(S_b[1], Y[1]) = (3,5) 的斜率是 5/3≈1.67⩽25/3 \approx 1.67 \leqslant 2,此后斜率只增,j=0j = 0 再也不会被选中。 第二,i=3i = 3 时队头没弹,因为斜率 (11−5)/(4−3)=6>3(11-5)/(4-3)=6 > 3;此时 j=1j = 1 的截距是 5−3⋅3=−45 - 3\cdot3 = -4,j=2j = 2 的是 11−3⋅4=−111 - 3\cdot4 = -1,前者更小,于是取 j=1j = 1 (这正是"只建 1、3 两站"的方案,花费 2+2+1⋅1=52 + 2 + 1\cdot1 = 5)。同时队尾把 j=2j = 2 弹掉: j=2j = 2 在 j=1j = 1 与 j=3j = 3 连线的上方,永远不可能成为最优决策。 第三,i=4i = 4 时斜率 17/5=3.4⩽417/5 = 3.4 \leqslant 4,轮到 j=1j = 1 被弹出,最优决策点右移到 j=3j = 3, 得到 f[4]=9f[4] = 9——恰好是样例要求的"选 1、3、4 建站"方案。

注意 i=3i = 3 时 j=2j = 2 虽然当时不是最优,但它是在队尾被弹掉的, 而不是队头;两处弹出的判据和含义完全不同(见上文)。

答案为什么是 f[n]f[n]。 所有牧场都必须被控制,而最东边的 nn 号牧场无法被任何 西边的站控制,所以 nn 必建站;f[n]f[n] 的定义正是"nn 建站时前 nn 个牧场全被控制", 它已经是覆盖全部牧场的最小值,不需要再对 ff 取 min⁡\min。

样例解释的对照。 样例选 1,3,41, 3, 4 建站,逐个控制站看它管了谁: 1 号站只管自己(a1=2a_1 = 2);3 号站管牧场 2 与自己,牧场 2 距离 3−2=13 - 2 = 1、放养量 11, 贡献 1×1=11 \times 1 = 1,加上 a3=2a_3 = 2 共 33;4 号站只在最东边管自己,付 a4=4a_4 = 4。 合计 2+(2+1×1)+4=92 + (2 + 1 \times 1) + 4 = 9,与题面的样例解释一致,也正是 DP 算出的 f[4]f[4]。

代码

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-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++ 版:

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-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 各一遍扫描,每个决策点最多入队一次、出队一次, 转移均摊 O(1)O(1),总时间 O(n)O(n)。
  • 空间:a,Sb,Skb,fa, S_b, S_{kb}, f 各一个长度 nn 的 long long 数组,加一个 O(n)O(n) 的队列, O(n)O(n)。n=106n = 10^6 时约 40 MB,低于 256 MB 限制。
  • 溢出边界:Skb[n]≈106×106×104/2=5×1015S_{kb}[n] \approx 10^6 \times 10^6 \times 10^4 / 2 = 5 \times 10^{15}, f[n]f[n] 在 101610^{16} 量级,必须全程 64 位。链式相乘的叉积最坏可以达到 ΔY⋅ΔX≈1016×1010=1026\Delta Y \cdot \Delta X \approx 10^{16} \times 10^{10} = 10^{26},已经越过 long long 的 9.2×10189.2 \times 10^{18},所以 main.cpp 的 bad() 把中间量声明为 __int128 作为保险。 (实测:把 __int128 换回 long long 后素材源的 10 组数据仍然全对, 说明该点的链上叉积尚未真的溢出——但它是坏数据下的确定性风险,保留 __int128。 Python 版整数无上限,天然安全。)
  • 与 C++ 版的关系:Python 版是同一算法的直接落地——前缀和增量维护、 队列用预分配 list + 头尾指针模拟,不依赖第三方库;每步只做常数次大整数运算, n=106n = 10^6 时大约需要数秒,可能吃满 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。 此外拿 n⩽40n \leqslant 40 的 400 组固定种子随机数据与 O(n2)O(n^2) 朴素 DP 对照,两版均无失配。

总结

  • 先让转移可读,再让转移变快:先把内层求和用两个前缀和压成 O(1)O(1), 式子里才浮出"斜率 ×\times 横坐标 + 常数"的形状,变量分离是斜率优化的入场券。
  • 两个单调性一个都不能少:横坐标 X[j]=Sb[j]X[j] = S_b[j] 严格递增来自 bk>0b_k > 0; 查询斜率 ii 严格递增来自"按牧场编号推进"。前者保证下凸壳无重复横坐标, 后者让队头弹出合法、让最优决策点单调右移。
  • 队头与队尾维护的是两件不同的事:队头弹的是"对当前及以后斜率都不再优"的点, 队尾弹的是"破坏下凸性"的点,写反或合并都会错。
  • 判定用叉积不用除法:避免浮点误差;而叉积在坏数据下会越出 long long, 所以 C++ 里把中间量声明为 __int128,这是零成本的安全边。
  • 答案是 f[n]f[n] 而不是 min⁡if[i]\min_i f[i]:因为最东边的牧场只能由自己建站来覆盖。

图示解析

下图直接用样例的 5 个决策点画出这件事。每个点是 (X[j],Y[j])=(Sb[j], f[j]+Skb[j])(X[j], Y[j]) = (S_b[j],\, f[j] + S_{kb}[j]), 横坐标越小表示越靠西;相邻两点连线上标的数字是它的斜率。

text
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

读图要点有三处。

第一,斜率单调递增就是下凸壳:保留下来的相邻斜率按 1.67→3.4→6.01.67 \to 3.4 \to 6.0 递增。 j=2j = 2 被弹掉后,j=1j = 1 直接连到 j=3j = 3,斜率是 22−58−3=3.4\dfrac{22-5}{8-3} = 3.4; 而原来的走向是 6.00→2.756.00 \to 2.75,斜率在下降,说明 j=2j = 2 是凸壳上的“上凸”点。

第二,查询斜率 ii 也在递增:i=2i = 2 时把斜率 1.671.67 对应的 j=0j = 0 弹掉 (1.67⩽21.67 \leqslant 2),i=4i = 4 时把斜率 3.43.4 对应的 j=1j = 1 弹掉(3.4⩽43.4 \leqslant 4)—— 被弹掉的斜率刚好都小于等于当次的 ii。于是队头指针从头到尾只向右走, 总移动次数不超过入队次数,这就是均摊 O(1)O(1) 的来源。

第三,横坐标严格递增自动成立:X[j]=Sb[j]X[j] = S_b[j] 每步至少增加 min⁡kbk⩾1\min_k b_k \geqslant 1, 所以图上不会出现两个点上下对齐,斜率不会退化成无穷。 这也解释了为什么这道题的斜率优化不需要像一般情形那样特判“横坐标相同”。