[NOIP 2009 普及组] 道路游戏

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

对角线前缀和 O(1) 查段收益，交换 max 后每条对角线单调队列滑动窗口，O(nm) 决策优化 DP。

OJ: luogu

题目 ID: P1070

难度:提高

标签:dp单调队列决策优化

创建: 2026-10-23 23:20

更新: 2026-10-23 23:35

形式化题目

环形马路有 $n$ 个机器人工厂（顺时针编号 $1 \sim n$ ，第 $i$ 段马路连接工厂 $i$ 与 $i+1$ ，第 $n$ 段连接 $n$ 与 $1$ ）。第 $j$ 个单位时间内，第 $i$ 段马路上有 $c[i][j]$ 枚金币。

机器人从工厂 $i$ 在时间 $s$ 买入、走 $k$ 步（ $1 \leqslant k \leqslant p$ ），第 $l$ 步过马路 $((i+l-1) \bmod n)$ ，收集该段在第 $s+l$ 个单位时间的金币。每段机器人走完后立即在任意工厂买入下一个机器人（瞬时，不消耗时间），环上同时只能有一个机器人。游戏恰进行 $m$ 个单位时间，各段步数之和恰为 $m$ 。

给定 $c[i][j]$ 与购买花费 $cost[i]$ ，求（收集金币总和 − 购买花费总和）的最大值。

样例

输入：

text

输出：

text

样例解释： $n = 2, m = 3, p = 2$ 。最优方案：在时间 $0$ 从工厂 $1$ 买入走 $2$ 步，收集 $c[1][1] + c[2][2] = 1 + 3 = 4$ ，花费 $cost[1] = 1$ ，净收益 $3$ ；在时间 $2$ 从工厂 $2$ 买入走 $1$ 步，收集 $c[2][3] = 4$ ，花费 $cost[2] = 2$ ，净收益 $2$ 。总计 $3 + 2 = 5$ 。

暴力解法

思路

把游戏看成「从时间 $dep$ 出发，先决定下一个机器人走几步、从哪个工厂出发」。用选择序列递归枚举所有分段方式与起点工厂组合，取最大值。

段间无位置衔接约束（新机器人可在任意工厂购买），所以不需要记录上一段结束时的工厂。每层递归选择「段长 $L \in [1, p]$ 」与「起点工厂 $i \in [0, n)$ 」，段收益用三重循环逐个 $l$ 累加。

代码

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
65
66
67
68
69
70
71
72
73
74/**
 * 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-23 23:20
 * update_at: 2026-10-23 23:34
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
//
// 直接按题意模拟：游戏恰进行 m 个单位时间，各段步数之和恰为 m；
// 每段由一个机器人走完，段长 L ∈ [1, p]，起点工厂 i ∈ [0, n) 任选。
// 机器人在时间 s 于工厂 i 买入、走 L 步，第 l 步过马路 (i+l-1) mod n，
// 收集 w[(i+l-1) mod n][s+l]，段收益 = 收金总和 - cost[i]。
//
// 用选择序列递归枚举所有分段方式与起点工厂组合，取最大值。
//
// 为什么只适合小数据：分段方式有 2^m 量级，每段再乘 n 个起点工厂，
// n=8, m=8 时已经很慢；只用于 n, m <= 8 的对拍。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 12;
const int MAXM = 12;

int n, m, p;
ll cost[MAXN];        // cost[i]：工厂 i 的购买花费（0-based）
ll w[MAXN][MAXM];     // w[road][tm]：第 tm 个时间第 road 段马路的金币
ll best_answer;       // 全局最优解

// 从工厂 start 出发走 L 步，收集的金币总和
// 步 l 过马路 (start+l-1) mod n，收 w[...][s+l]
ll walk_gain(int start, int s, int L) {
    ll sum = 0;
    for (int l = 1; l <= L; l++) {
        int road = (start + l - 1) % n;
        sum += w[road][s + l];
    }
    return sum;
}

// 选择序列递归：dep 是当前时间（下一个机器人买入的时刻），已走完 dep 个时间单位
// 这一层在选择「下一个机器人走几步、从哪个工厂出发」
void dfs(int dep, ll cur) {
    if (dep == m) {
        if (cur > best_answer) best_answer = cur;
        return;
    }
    int maxL = min(p, m - dep);
    for (int L = 1; L <= maxL; L++) {
        for (int i = 0; i < n; i++) {
            ll g = walk_gain(i, dep, L) - cost[i];
            dfs(dep + L, cur + g);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> p;
    for (int road = 0; road < n; road++) {
        for (int tm = 1; tm <= m; tm++) {
            cin >> w[road][tm];
        }
    }
    for (int i = 0; i < n; i++) cin >> cost[i];

    best_answer = -(1LL << 60);
    dfs(0, 0);
    cout << best_answer << "\n";
    return 0;
}

复杂度

时间：分段方式有 $2^m$ 量级，每段再乘 $n$ 个起点工厂，指数级。空间： $O(m)$ 递归栈。

只适合 $n, m \leqslant 8$ 的小数据与对拍。

瓶颈

枚举所有分段方式与起点工厂，没有利用「段收益只依赖 (起点工厂, 开始时间, 长度)」这一结构性质，也没有用前缀和加速段收益查询。

DP + 对角前缀和

思路

观察：机器人从工厂 $i$ 在时间 $s$ 出发走 $k$ 步，第 $l$ 步过马路 $(i+l-1) \bmod n$ 、收第 $s+l$ 时间的金币。令 $u \equiv (\mathrm{road} - \mathrm{time}) \pmod n$ ，则每一步都落在同一条对角线 $u = (i - 1 - s) \bmod n$ 上，收益沿对角线连续累加。

定义对角线前缀和 $D[u][t]$ = 对角线 $u$ 上「时间 $\leqslant t$ 」的金币前缀和，则段收益 $= D[u][s+k] - D[u][s]$ ， $O(1)$ 查询。

设 $f[t]$ 表示前 $t$ 个时间单位全部走完的最大净收益（ $f[0] = 0$ ）：

f[t] = \max_{k=1}^{\min(p,t)} \Big( f[t-k] + \max_{i=0}^{n-1} \big( D[u][t] - D[u][t-k] - cost[i] \big) \Big)

其中 $u = (i - 1 - (t-k)) \bmod n$ 。

用对角前缀和消掉内层 $l$ 循环，但 $\max_i$ 与 $\max_k$ 仍是三重循环。

代码

不单独给出（与正解共享对角前缀和预处理，转移部分是正解的未优化版本）。

复杂度与瓶颈

时间： $O(n \cdot m \cdot p)$ ， $n = m = p = 1000$ 时 $10^9$ ，不稳健。空间： $O(n \cdot m)$ 。

瓶颈： $\max_i$ 与 $\max_k$ 无法分离，对固定的 $t$ 与 $k$ ， $\max_i$ 被反复重算。

正解

关键观察

交换 $\max_s$ 与 $\max_u$ （逐点对每个 $t$ 合法）：

f[t] = \max_{u} \Big( D[u][t] + \max_{s \in [t-p,\ t-1]} h_u(s) \Big)

其中 $h_u(s) = f[s] - D[u][s] - cost[(u+s+1) \bmod n]$ 。

核心： $h_u(s)$ 只依赖 $(u, s)$ ，与 $t$ 无关！窗口 $[t-p, t-1]$ 随 $t$ 单调右移，对每个 $u$ 维护一个单调队列做滑动窗口最大值。

思路

预处理对角线前缀和 $D[u][t]$ ， $O(n \cdot m)$ 。
逐 $t$ 求 $f[t]$ ：
- 先把 $s = t-1$ 入队（ $f[t-1]$ 已知），计算 $h_u(t-1)$ 并维护单调队列。
- 用当前队列的队首（窗口内最大 $h_u$ ）更新 $f[t]$ 。
答案 $= f[m]$ 。

入队顺序关键：先把 $s = t-1$ 入队，再算 $f[t]$ ，这样 $h_u(t-1)$ 参与 $f[t]$ 及之后的计算，而 $h_u(t)$ 要等下一轮才入队。

代码

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
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
102
103
104
105
106
107
108
109
110
111/**
 * 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-23 23:20
 * update_at: 2026-10-23 23:34
 */
// main.cpp：P1070 道路游戏 正解（决策优化，O(n*m)）。
//
// 状态定义：
//   f[t] = 前 t 个时间单位全部走完（各段步数之和恰为 t）的最大净收益，f[0] = 0。
//
// 关键观察（对角线不变量）：
//   时间 s 在工厂 i 买入、走 k 步，第 l 步过马路 (i+l-1) mod n，
//   收集 w[(i+l-1) mod n][s+l]。令 u ≡ (road - time) (mod n)，
//   则「马路下标 - 时间下标」≡ u 恒定，收益沿对角线 u 连续：
//       Σ_l w[...][s+l] = D[u][s+k] - D[u][s]
//   其中 D[u][t] = 对角线 u 上「时间 <= t」的金币前缀和。
//   反过来给定 (u, s) 时 i = (u + s + 1) mod n 唯一确定，所以购买花费可写成 cost[(u+s+1) mod n]。
//
// 转移：
//   f[t] = max_{s ∈ [t-p, t-1]} ( f[s] + max_u ( D[u][t] - D[u][s] - cost[(u+s+1) mod n] ) )
//        = max_u ( D[u][t] + max_{s ∈ [t-p, t-1]} h_u(s) )
//   其中 h_u(s) = f[s] - D[u][s] - cost[(u+s+1) mod n] 只依赖 (u, s)、与 t 无关。
//
//   ⚠ 交换 max 合法性：max_s max_u == max_u max_s 是逐点（对每个 t）成立的，
//     因此外层枚举 t、内层枚举 u；不能把 u 放外层，否则 h_u(s) 用到的 f[s]
//     可能还没算完（s < t 但 f[s] 还会被后面的 u' 更新）。
//
//   窗口 [t-p, t-1] 随 t 单调右移，对每条对角线 u 维护一个单调队列做
//   滑动窗口最大值。求完 f[t] 后再把 h_u(t) 入队（因为 h_u(t) 影响的是 t'>t）。
//   总复杂度 O(n*m)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1005;         // 工厂 / 马路上限
const int MAXM = 1005;         // 时间上限
const int DIAG_SHIFT = MAXM;   // u 平移量，保证下标非负
const int MAXU = DIAG_SHIFT + MAXN + 5; // 对角线截距 u 平移后的数组上界

int n, m, p;
ll cost[MAXN];        // cost[i]：在第 i 个工厂购买机器人的花费（0-based，与时间无关）
ll w[MAXN][MAXM];     // w[road][tm]：第 tm 个单位时间第 road 段马路上的金币
ll diag[MAXU][MAXM];  // diag[u][t]：对角线 u 上「时间 <= t」的金币前缀和
ll f[MAXM];           // f[t]：前 t 个时间单位的最大净收益

// 对角线编号：u ≡ (road - time) (mod n)，取代表元后平移 DIAG_SHIFT
inline int diag_id(int road, int tm) {
    int u = ((road - tm) % n + n) % n;
    return u + DIAG_SHIFT;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> p;
    for (int road = 0; road < n; road++) {
        for (int tm = 1; tm <= m; tm++) {
            cin >> w[road][tm];
        }
    }
    for (int i = 0; i < n; i++) cin >> cost[i];

    // 1) 对角线前缀和：diag[u][tm] = diag[u][tm-1] + 该时间落在对角线 u 上的金币
    //    每个时间 tm 恰好有 n 个马路各贡献 1 个金币，分别落在 n 条对角线上（互不重复）。
    for (int u = 0; u < MAXU; u++) diag[u][0] = 0;
    for (int tm = 1; tm <= m; tm++) {
        for (int u = 0; u < MAXU; u++) diag[u][tm] = diag[u][tm - 1];
        for (int road = 0; road < n; road++) {
            int u = diag_id(road, tm);
            diag[u][tm] += w[road][tm];
        }
    }

    // 2) DP：f[0] = 0；f[t] 初值取 -inf，表示「还没算出来」
    f[0] = 0;
    for (int t = 1; t <= m; t++) f[t] = -(1LL << 60);

    // 3) 逐 t 求 f[t]；内层枚举对角线 u，外层枚举 t。
    //    对每个 u 一个单调队列，队列内容只增不减（下标单调递增，hval 递减）。
    //    ⚠ 顺序关键：先把 s = t-1 入队（f[t-1] 已知），再用当前队列算 f[t]。
    static int qidx[MAXN][MAXM]; // qidx[u][k]：对角线 u 的队列第 k 个候选的下标 s
    static int qhead[MAXN], qtail[MAXN]; // 队列头尾（左闭右开）
    static ll hval[MAXN][MAXM]; // hval[u][s]：对角线 u 在 s 处的候选值

    for (int t = 1; t <= m; t++) {
        // 3.1) 把 s = t-1 加入候选（f[t-1] 已知）；t=1 时即 f[0]=0 的基线
        for (int u = 0; u < n; u++) {
            int s = t - 1;
            int i = (u + s + 1) % n; // i = (u + s + 1) mod n
            hval[u][s] = f[s] - diag[u + DIAG_SHIFT][s] - cost[i];
            while (qtail[u] > qhead[u] && hval[u][qidx[u][qtail[u] - 1]] <= hval[u][s]) qtail[u]--;
            qidx[u][qtail[u]] = s;
            qtail[u]++;
        }
        // 3.2) 用已知 f[s] (s < t) 更新 f[t]：对每个 u 求滑动窗口最大值，取全局最大
        for (int u = 0; u < n; u++) {
            while (qhead[u] < qtail[u] && qidx[u][qhead[u]] < t - p) qhead[u]++;
            if (qhead[u] < qtail[u]) {
                int s = qidx[u][qhead[u]];
                ll cand = diag[u + DIAG_SHIFT][t] + hval[u][s];
                if (cand > f[t]) f[t] = cand;
            }
        }
    }

    cout << f[m] << "\n";
    return 0;
}

复杂度

时间： $O(n \cdot m)$ ， $n = m = 1000$ 时约 $10^6$ ，实测 29ms。空间： $O(n \cdot m)$ ，实测 37.8MB。

总结

本题的关键是对角线不变量：机器人走的每一步都落在同一条「马路 − 时间」对角线上，收益沿对角线连续累加，用前缀和 $O(1)$ 查询段收益。进一步观察到 $h_u(s)$ 与 $t$ 无关，交换 $\max$ 后对每条对角线用单调队列做滑动窗口最大值，把 $O(nmp)$ 降到 $O(nm)$ 。

三层解法的关系：

暴力层：枚举分段方式与起点工厂，暴露「段与段之间只共享结束时间」的 DP 无后效性。
DP + 对角前缀和：用前缀和消掉内层 $l$ 循环，但 $\max_i$ 与 $\max_k$ 仍是三重循环。
决策优化：交换 $\max$ + 单调队列，把三重循环降到两重， $O(nm)$ 过全部数据。

P1070 [NOIP 2009 普及组] 道路游戏

题目描述

小新正在玩一个简单的电脑游戏。

游戏中有一条环形马路，马路上有 $n$ 个机器人工厂，两个相邻机器人工厂之间由一小段马路连接。小新以某个机器人工厂为起点，按顺时针顺序依次将这 $n$ 个机器人工厂编号为 $1\sim n$ ，因为马路是环形的，所以第 $n$ 个机器人工厂和第 $1$ 个机器人工厂是由一段马路连接在一起的。小新将连接机器人工厂的这 $n$ 段马路也编号为 $1\sim n$ ，并规定第 $i$ 段马路连接第 $i$ 个机器人工厂和第 $i+1$ 个机器人工厂（ $1\le i\le n-1$ ），第 $n$ 段马路连接第 $n$ 个机器人工厂和第 $1$ 个机器人工厂。

游戏过程中，每个单位时间内，每段马路上都会存在一些金币（不同时间段互不干扰），金币的数量会随着时间发生变化，即不同单位时间内同一段马路上的金币数量可能是不同的。小新需要机器人的帮助才能收集到马路上的金币。所需的机器人必须在机器人工厂用一些金币来购买，机器人一旦被购买，便会沿着环形马路按顺时针方向一直行走，在每个单位时间内行走一次，即从当前所在的机器人工厂到达相邻的下一个机器人工厂，并将经过的马路上的所有金币收集给小新，例如，小新在 $i$ （ $1\le i\le n$ ）号机器人工厂购买了一个机器人，这个机器人会从 $i$ 号机器人工厂开始，顺时针在马路上行走，第一次行走会经过 $i$ 号马路，到达 $i+1$ 号机器人工厂（如果 $i=n$ ，机器人会到达第 $1$ 个机器人工厂），并将 $i$ 号马路上的所有金币收集给小新。游戏中，环形马路上不能同时存在 $2$ 个或者 $2$ 个以上的机器人，并且每个机器人最多能够在环形马路上行走 $p$ 次。小新购买机器人的同时，需要给这个机器人设定行走次数，行走次数可以为 $1\sim p$ 之间的任意整数。当马路上的机器人行走完规定的次数之后会自动消失，小新必须立刻在任意一个机器人工厂中购买一个新的机器人，并给新的机器人设定新的行走次数。

以下是游戏的一些补充说明：

游戏从小新第一次购买机器人开始计时。
购买机器人和设定机器人的行走次数是瞬间完成的，不需要花费时间。
购买机器人和机器人行走是两个独立的过程，机器人行走时不能购买机器人，购买完机器人并且设定机器人行走次数之后机器人才能行走。
在同一个机器人工厂购买机器人的花费是相同的，但是在不同机器人工厂购买机器人的花费不一定相同。
购买机器人花费的金币，在游戏结束时再从小新收集的金币中扣除，所以在游戏过程中小新不用担心因金币不足，无法购买机器人而导致游戏无法进行。也因为如此，游戏结束后，收集的金币数量可能为负。

现在已知每段马路上每个单位时间内出现的金币数量和在每个机器人工厂购买机器人需要的花费，请你告诉小新，经过 $m$ 个单位时间后，扣除购买机器人的花费，小新最多能收集到多少金币。

输入格式

第一行 $3$ 个正整数 $n,m,p$ ，意义如题目所述。

接下来的 $n$ 行，每行有 $m$ 个正整数，每两个整数之间用一个空格隔开，其中第 $i$ 行描述了 $i$ 号马路上每个单位时间内出现的金币数量（ $1\le $ 金币数量 $\le 100$ ），即第 $i$ 行的第 $j$ （ $1\le j\le m$ ）个数表示第 $j$ 个单位时间内 $i$ 号马路上出现的金币数量。

最后一行，有 $n$ 个整数，每两个整数之间用一个空格隔开，其中第 $i$ 个数表示在 $i$ 号机器人工厂购买机器人需要花费的金币数量（ $1\le $ 金币数量 $\le 100$ ）。

输出格式

共一行，包含 $1$ 个整数，表示在 $m$ 个单位时间内，扣除购买机器人花费的金币之后，小新最多能收集到多少金币。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

对于 $40\%$ 的数据， $2\le n\le 40$ ， $1\le m\le 40$ 。

对于 $90\%$ 的数据， $2\le n\le 200$ ， $1\le m\le 200$ 。

对于 $100\%$ 的数据， $2\le n\le 1000$ ， $1\le m\le 1000$ ， $1\le p\le m$ 。

NOIP 2009 普及组第四题

[NOIP 2009 普及组] 道路游戏

目录

形式化题目

样例

暴力解法

思路

代码

复杂度

瓶颈

DP + 对角前缀和

思路

代码

复杂度与瓶颈

正解

关键观察

思路

代码

复杂度

总结