「Fence」围栏

形式化题目

有 $N$ 块木板排成一行（位置 $1 \dots N$ ）和 $M$ 个工匠。工匠 $i$ 由三个整数刻画：

$S_i$ ：他必须覆盖的木板位置；
$L_i$ ：他最多能连续粉刷的木板数；
$P_i$ ：他每粉刷一块木板得到的报酬。

每个工匠要么完全不粉刷，要么恰好粉刷一个包含第 $S_i$ 块、长度不超过 $L_i$ 的连续区间 $[k,j]$ ：

k \leqslant S_i \leqslant j, \qquad j - k + 1 \leqslant L_i,

并获得 $P_i \cdot (j-k+1)$ 的报酬。每块木板至多被粉刷一次（可以留白）。求总报酬的最大值。

题面保证 $1 \leqslant N \leqslant 16000$ ， $1 \leqslant M \leqslant 100$ ， $1 \leqslant P_i \leqslant 10000$ ，且不同工匠的 $S_i$ 互不相同。

以样例为例：

text

1
2
3N = 8，M = 4
工匠 1: L=3 P=2 S=2     工匠 3: L=3 P=3 S=5
工匠 2: L=3 P=2 S=3     工匠 4: L=1 P=1 S=7

一种最优安排是：工匠 1 刷 $[1,2]$ 得 $2 \times 2 = 4$ ，工匠 2 刷 $[3,4]$ 得 $2 \times 2 = 4$ ，工匠 3 刷 $[5,7]$ 得 $3 \times 3 = 9$ ，工匠 4 不刷 —— 三段两两不交、各自盖住自己的 $S_i$ 、长度都不超过 $L_i$ ，总报酬 $4 + 4 + 9 = $ 17。

正解

思路

先排序。 每个工匠的区间都含 $S_i$ ，而区间之间两两不交，所以把所有区间按右端点排序后，工匠的出现顺序必然与 $S_i$ 升序一致：区间 $[k,j]$ 含 $S_i$ ，它右边的区间起点 $> j \geqslant S_i$ ，只能属于 $S$ 更大的工匠。于是按 $S_i$ 升序处理工匠不会漏解，题面「不同工匠的 $S_i$ 不同」正是为了让这个顺序唯一、排序无歧义。

状态与三类转移。 设

f[i][j] = \text{前 } i \text{ 个工匠只在前 } j \text{ 块木板上作业能取得的最大报酬}.

看第 $i$ 个工匠的最终选择，三类互斥且穷尽：

他不刷： $f[i-1][j]$ ；
他刷了，但右端点 $< j$ ：他的整个区间落在前 $j-1$ 块里，归入 $f[i][j-1]$ ；
他刷的区间右端点恰好是 $j$ ，左端点为 $k$ ：报酬 $f[i-1][k-1] + P_i\,(j-k+1)$ 。

第 3 类里 $k$ 受两个条件夹住：区间要盖住 $S_i$ 给出 $k \leqslant S_i$ ；长度不超过 $L_i$ 给出 $k \geqslant j - L_i + 1$ 。于是

f[i][j] = \max\Bigl(\; f[i-1][j],\;\; f[i][j-1],\;\; \max_{k \in [\,j-L_i+1,\; S_i\,]} \bigl(f[i-1][k-1] + P_i(j-k+1)\bigr) \Bigr).

注意 $j < S_i$ 时合法区间为空，第三类不产生候选。

瓶颈。 照着上式实现，枚举 $k$ 是额外的一层循环，复杂度 $O(N^2M) = 2.56 \times 10^{10}$ ，在 1 s 的限时下完全不可行。能否把「枚举 $k$ 取最值」变成「维护最值」？

代入 $m = k-1$ 拆开与 $j$ 无关的部分。 令 $m = k - 1$ ，它表示「刷之前已经安排好的木板数」。条件 $k \in [j-L_i+1, S_i]$ 等价于 $m \in [j - L_i,\; S_i - 1]$ ，而

f[i-1][k-1] + P_i(j-k+1) = f[i-1][m] + P_i(j-m) = P_i j + \bigl(f[i-1][m] - P_i m\bigr).

$P_i j$ 与 $m$ 无关，可以提到 $\max$ 外面：

f[i][j] = \max\Bigl(\; f[i-1][j],\;\; f[i][j-1],\;\; P_i j + \max_{m \in [\,j-L_i,\; S_i-1\,]} \bigl(f[i-1][m] - P_i m\bigr) \Bigr).

决策区间在滑动。 关键的最后一步观察：这个窗口的右端 $S_i-1$ 恒定不动，左端 $j-L_i$ 随 $j$ 单调右移——

text

1
2
3
4m:   0    1    2   ...  S_i-1   S_i  ...
          [============]          j = S_i    窗口 m ∈ [S_i-L_i, S_i-1]
              [============]      j = S_i+1  左端右移一位
                  [============]  j 再变大   左端继续右移，右端不动

这正是单调队列的适用条件：候选区间只在一端进出，且要维护区间内的最大值。队列中按 $m$ 递增存放 $\bigl(f[i-1][m] - P_i m,\; m\bigr)$ 并保持值单调递减：

插入： $m$ 小、值又不大于新元素的候选，既更早过期又更差，可以弹掉；
过期： $m < j - L_i$ 的队首弹出，因为从它起刷已经超过长度限制；
查询：弹完以后队首的值就是窗口最大值，配上 $P_i j$ 即为第三类的最优值。

Python 实现上的两点简化。 因为右端固定为 $S_i-1$ ，可以把 $m \in [0, S_i-1]$ 全部候选在进入主循环之前一次性入队，主循环里只做「弹过期队首 + 取队首」。另外 $f[i][\cdot]$ 只依赖 $f[i-1][\cdot]$ 与自身的 $f[i][j-1]$ ，所以 $i$ 这一维用两张长度 $N+1$ 的列表滚动即可，空间从 $O(NM)$ 降到 $O(N)$ 。

样例推演

把样例按 $S$ 排序后就是输入顺序。下表是完整的 $f$ 表，行是处理完第 $i$ 个工匠，列是前缀长度 $j$ ：

行	工匠 $(L,P,S)$	2	3	4	5	6	7	8
$i=0$	无	0	0	0	0	0	0	0
$i=1$	$(3,2,2)$	4	6	6	6	6	6	6
$i=2$	$(3,2,3)$	4	6	8	10	10	10	10
$i=3$	$(3,3,5)$	4	6	8	13	15	17	17
$i=4$	$(1,1,7)$	4	6	8	13	15	17	17

读表要点：第 $i=1$ 行 $f[1][2]=4$ 表示第一个工匠刷 $[1,2]$ 得 4 分——这个窗口下队首是 $m=0$ ，也就是从第 1 块开始刷； $f[1][3]=6$ 是他刷 $[1,3]$ （长度刚好用满 $L_1=3$ ）得 $2\times3=6$ 。他一个人最多只能得 $L_1 P_1 = 6$ 分，所以 $j \geqslant 3$ 以后 $f[1][j]$ 一直保持 6，多的木板宁可空着；这也解释了为什么 $f[1][j]$ 从某列起就靠 $f[1][j-1]$ 平推。第 $i=3$ 行 $f[3][7] = 17$ 是答案的前身：第三个工匠取 $m = 4$ ，即前 4 块由前两个工匠最优安排（ $f[2][4]=8$ ，工匠 2 刷 $[3,4]$ ），他自己从第 5 块刷到第 7 块，得 $8 + 3 \times 3 = 17$ 。答案 $f[4][8] = 17$ 说明第四个工匠 $(L,P,S)=(1,1,7)$ 没法在不冲突的前提下再加分。

再看 $i=1$ 时单调队列的实际工作过程（队列键为 $f[0][m] - 2m$ ，窗口是 $m \in [j-3,\,1]$ ）：

$j$	候选窗口 $m$	队首 $m$	第三类取值	$f[1][j]$
2	$[-1, 1]$	0	$0 + 2\times2 = 4$	4
3	$[0, 1]$	0	$0 + 2\times3 = 6$	6
4	$[1, 1]$	1	$-2 + 2\times4 = 6$	6
5	$[2, 1]$ 空	—	无候选	6

可以看到第 4 列在 $j=4$ 时队首从 $m=0$ 换成 $m=1$ ，之后 $j > S_i + L_i - 1 = 2 + 3 - 1 = 4$ 时窗口彻底为空——这正是「长度不得超过 $L_i$ 」在代码里的体现。

代码

代码里的命名与公式的对应关系：must_paint $=S_i$ 、limit $=L_i$ 、price $=P_i$ ， best 是上一轮的 $f[i-1][\cdot]$ ，cur 是本轮的 $f[i][\cdot]$ ，window 就是那个单调队列。

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

typedef long long ll;

const int MAXN = 16005;
const int MAXM = 105;

struct Painter {
    ll limit; // L：最多连续粉刷的木板数
    ll price; // P：每块木板的报酬
    ll must;  // S：必须覆盖的木板位置
};

ll n, m;
Painter painter[MAXM]; // 全部工匠，按 S 升序排列后依次加入 DP
ll best[MAXN];         // best[j]：已加入的工匠在「前 j 块木板」上能拿到的最大报酬
ll cur[MAXN];          // 加入当前工匠后的新报酬表

bool cmp_must(const Painter &a, const Painter &b) { return a.must < b.must; }

// 让一个工匠（必刷 must、一次最多刷 limit 块、每块 price）加入后，更新报酬表。
// 新表先继承 best（这个工匠不刷，或刷的段不含第 j 块）；另一种情况是他刷的段右端正好是 j，
// 左端为 k，需满足 k <= must（段要盖住必刷的那块）和 k >= j-limit+1（长度受限），
// 收益 best[k-1] + (j-k+1)*price = price*j + (best[m] - price*m)，其中 m = k-1。
// m 的窗口是 [j-limit, must-1]，j 增大时窗口右端固定、左端右移，用单调队列维护窗口最值。
void add_painter(const Painter &p) {
    for (ll j = 0; j <= n; j++) cur[j] = best[j];
    deque<pair<ll, ll> > win; // (best[m] - price*m, m)，值从队首到队尾单调递减
    for (ll t = 0; t < p.must; t++) {
        ll value = best[t] - p.price * t;
        while (!win.empty() && win.back().first <= value) win.pop_back();
        win.push_back(make_pair(value, t));
    }
    for (ll j = p.must; j <= n; j++) {
        while (!win.empty() && win.front().second < j - p.limit) win.pop_front();
        if (!win.empty()) {
            ll brushed = win.front().first + p.price * j; // 这个工匠刷 [k, j] 的收益
            if (brushed > cur[j]) cur[j] = brushed;
        }
        if (cur[j - 1] > cur[j]) cur[j] = cur[j - 1]; // 「前 j 块」可退化成「前 j-1 块」
    }
    for (ll j = 0; j <= n; j++) best[j] = cur[j];
}

int main() {
    scanf("%lld%lld", &n, &m);
    for (ll i = 0; i < m; i++)
        scanf("%lld%lld%lld", &painter[i].limit, &painter[i].price, &painter[i].must);
    // 按 S 排序后，每个工匠刷的段都排在后面工匠要盖住的 S 之前，逐行 DP 才成立
    sort(painter, painter + m, cmp_must);
    for (ll i = 0; i < m; i++) add_painter(painter[i]);
    printf("%lld\n", best[n]);
    return 0;
}

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#!/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-01 21:32
# update_at: 2026-10-01 21:40

import sys
from collections import deque


def add_painter(best: list[int], limit: int, price: int, must_paint: int) -> list[int]:
    """让一个工匠（必刷 must_paint、一次最多刷 limit 块、每块 price）加入后，返回新的报酬表。

    best[j] 是已安排的工匠在「前 j 块木板」上能拿到的最大报酬。新表先继承 best：
    这个工匠不刷，或者刷的那一段不包含第 j 块木板。剩下的一种情况是「他刷的段右端正好是 j」，
    设左端为 k，k 必须满足 k <= must_paint（段要盖住必刷的那块）和 k >= j-limit+1（长度受限），
    收益为 best[k-1] + (j-k+1)*price = price*j + (best[k-1] - price*(k-1))。
    右边只有 price*j 随 j 变化，所以每块木板只需在窗口 m = k-1 ∈ [j-limit, must_paint-1] 里
    取 best[m] - price*m 的最大值；j 增大时窗口左端右移、右端不动，用单调队列维护即可。
    """
    n = len(best) - 1
    cur = best[:]                 # 先承接「不刷」和「刷的段不含第 j 块」两种可能
    window = deque()              # (best[m] - price*m, m)，值从队首到队尾单调递减
    for m in range(must_paint):   # 窗口右端恒为 must_paint-1，候选一次性入队
        value = best[m] - price * m
        while window and window[-1][0] <= value:
            window.pop()
        window.append((value, m))
    for j in range(must_paint, n + 1):
        while window and window[0][1] < j - limit:  # 从这些起点起刷，长度已超过 limit
            window.popleft()
        if window:
            brushed = window[0][0] + price * j
            if brushed > cur[j]:
                cur[j] = brushed
        if cur[j - 1] > cur[j]:                     # 「前 j 块」可退化成「前 j-1 块」
            cur[j] = cur[j - 1]
    return cur


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)

    fences: list[tuple[int, int, int]] = []  # (limit, price, must_paint)，即题面的 (L, P, S)
    for _ in range(m):
        limit, price, must_paint = next(data), next(data), next(data)
        fences.append((limit, price, must_paint))
    # 按 S 排序后，每个工匠刷的段都排在后面工匠要盖住的 S 之前，逐行 DP 才成立
    fences.sort(key=lambda fence: fence[2])

    best = [0] * (n + 1)
    for limit, price, must_paint in fences:
        best = add_painter(best, limit, price, must_paint)
    print(best[n])


if __name__ == "__main__":
    solve()

复杂度

排序： $O(M \log M)$ ；
DP：每个工匠对 $j$ 扫一遍 $[S_i, N]$ ，队列入队/出队各至多 $N+1$ 次，均摊 $O(N)$ ，总计 $O(NM)$ ；
空间：两张长度 $N+1$ 的表加一个队列， $O(N + M)$ 。

$N M = 1.6 \times 10^{6}$ ，实测最大数据组（ $N = 16000$ 、 $M = 100$ ）用时约 0.12 s、峰值内存 17 MB，远低于 1000 ms / 128 MB 的限制。

总结

按 $S_i$ 排序后，每个工匠的区间都落在后面工匠必刷的 $S$ 左侧，「前 $i$ 个工匠处理前 $j$ 块」这个线性 DP 才成立。
三类转移中只有第三类需要枚举段左端；代入 $m = k-1$ 后收益拆成与 $j$ 无关的 $P_i j$ 和只与 $m$ 有关的 $f[i-1][m] - P_i m$ ，把枚举变成求窗口最值。
决策窗口 $[j-L_i,\, S_i-1]$ 的右端固定、左端单调右移，是单调队列的标准信号；右端固定这一点还让候选可以一次性入队，主循环只剩弹队首与读队首。
空间上只需滚动 $f$ 的 $i$ 维， $O(N)$ 即可。
边界： $j < S_i$ 时窗口为空、只保留前两类转移； $j > S_i + L_i - 1$ 时队列会被弹空，同样自动退化为前两类转移。

图示解析

这张图串起本题从建模到得到答案的主线：

text

1
2
3
4
5
6
7
8
9
10
11N 块木板 + M 个工匠（各刷一段连续区间，两两不交）
`- 按 S 排序：区间按右端点有序，DP 可线性推进
   `- 状态 f[i][j] = 前 i 个工匠、只在前 j 块上的最大报酬
      |- 三类转移
      |  |- 不刷            -> f[i-1][j]
      |  |- 刷的段不含第 j 块 -> f[i][j-1]
      |  `- 刷的段右端是 j    -> max_k f[i-1][k-1] + P*(j-k+1)
      `- 第三类代入 m = k-1
         |- 拆出 P*j 与 f[i-1][m] - P*m
         |- 窗口 [j-L, S-1]：右端不动、左端单调右移
         `- 单调队列维护窗口最大值 -> O(NM)

先看每个节点代表的推理结论：排序解决「按什么顺序决策」，状态定义解决「子问题怎么划分」，三类转移穷尽一个工匠的所有选择，而展开与窗口滑动则是把 $O(N)$ 的枚举降成 $O(1)$ 均摊的关键。最后顺着分支检查单调队列的两条不变式（值递减、下标递增）是否同时支撑了「取最大」与「判过期」。

「Fence」 围栏

目录

形式化题目

正解

思路

样例推演

代码

复杂度

总结

图示解析