形式化题目

环上有 $n$ 段马路首尾相接：第 $i$ 段连接工厂 $i$ 与 $i+1$（第 $n$ 段连接工厂 $n$ 与 $1$）。给定 $m$ 个单位时间，第 $i$ 段马路在第 $t$ 个单位时间出现 $g[i][t]$ 枚金币；在工厂 $f$ 购买机器人需要花费 $\text{cost}[f]$。

机器人在工厂瞬时购买并设定行走次数（$1 \sim p$ 之间的整数），随后每个单位时间顺时针走过一段马路，并收走所走马路当刻的全部金币。环上任一时刻最多只能有 $1$ 个机器人；机器人走完设定次数立即消失，必须立刻在任意工厂购买下一个机器人（同样瞬时）。游戏从第一次购买开始计时，走满 $m$ 个单位时间结束，最终用收集的金币总数减去所有购买花费（过程里不看余额，故答案可能为负）。求可达到的最大净收益。

样例（$n=2,\ m=3,\ p=2$）的金币分布如下，工厂购买花费依次为 $1$、$2$：

这张表里一次行程同时向右、向下移动：$t=1$ 在工厂 1 买的机器人走 2 步，收走「1 号马路 @ 时刻 1」和「2 号马路 @ 时刻 2」，在表中恰是一条右下方向的对角线。要观察的重点是：同一段行程经过的「马路编号 − 时刻」保持不变，这正是后面全部优化的来源。样例的最优方案为 $t=1$ 在工厂 1 买机器人走 2 步（收 $1+3$），$t=3$ 再在工厂 1 买机器人走 1 步（收 $3$），净收益 $1+3+3-1-1 = 5$。

正解

思路

朴素做法：按时间分段 DP。 由题意，任何合法玩法都恰好把时间轴 $1,\dots,m$ 无缝切成若干连续段，每段长度 $L \in [1, \min(p,\ \text{剩余时间})]$，每段对应一个从某工厂出发的机器人；段与段之间没有状态耦合——下一段可以在任意工厂重新购买。因此只需一维状态：$dp[j]$ 表示走完前 $j$ 个单位时间能拿到的最大净收益，$dp[0]=0$，答案为 $dp[m]$。枚举最后一段覆盖的时间 $[k+1, j]$ 与该段起点工厂 $f$（$0$ 下标）：

三重枚举是 $O(nmp)$，$n=m=p=1000$ 时最坏 $10^9$，不可行。

瓶颈在哪。 转移里的行程金币和：一段行程同时沿「马路编号」和「时刻」两个方向前进，两个下标一起平移，一维前缀和套不上，朴素求和把 $O(p)$ 的内层求和留在了热循环里。

关键观察：一次行程沿「对角线」前进。 时刻 $s$ 从工厂 $f$ 出发的机器人，时刻 $t$ 走的马路是 $(f + t - s) \bmod n$——整段行程中「马路编号 − 时刻」模 $n$ 恒定。把这个差记作 $c-1$，即对角线编号 $c = (f - s + 1) \bmod n$（可以理解成：这条路径若延伸回时刻 1，会经过的马路编号），于是：

• 时刻 $t$ 在对角线 $c$ 上走的马路唯一确定：$(t + c - 1) \bmod n$；
• 段起点工厂也由 $k$、$c$ 决定：$f = (s + c - 1) \bmod n = (k + c) \bmod n$（$s = k+1$，机器人出发时走的第一段马路就是它所在的工厂）。

对角线前缀和拆分转移。 对每条对角线按时刻建前缀和 $P_c[t] = \sum_{u=1}^{t} g\big[(u + c - 1) \bmod n\big][u]$（$P_c[0]=0$），段 $[k+1, j]$ 的金币和即 $P_c[j] - P_c[k]$，$O(1)$ 求出。把只含 $j$ 的项提到内层外面：

滑动窗口 + 单调队列。 固定对角线 $c$ 后，内层就是标准的滑动窗口最大值：$j$ 递增时窗口 $[\max(0,\,j-p),\ j-1]$ 的两端都单调右移，长度不超过 $p$。每条对角线维护一个单调队列存 $(k, V_c[k])$ 并保持 $V$ 递减：新值入队时弹出所有不大于它的队尾（窗口右移后它们只会更早过期，永无出头之日），队头下标离开窗口就弹出队头，队头即当前窗口最大值，均摊 $O(1)$。外层按 $j = 1 \dots m$ 推进：每步先把 $k = j-1$ 的 $V$ 压入各队列，再用 $P_c[j] + \text{队头}$ 更新 $dp[j]$。$P_c$ 不必存全表，每轮加一次当刻金币滚动维护即可。

样例推演。 对角线前缀和为 $P_0 = (1, 4, 7)$、$P_1 = (2, 4, 8)$（$c=0$ 依次走 1 号马路@1、2 号马路@2、1 号马路@3；$c=1$ 依次走 2 号马路@1、1 号马路@2、2 号马路@3），各步转移如下：

表中 $V$ 的花费下标是 $(k+c) \bmod 2$，即 0 号工厂花 $1$、1 号工厂花 $2$。$j=2$ 的胜者是 $c=0,\,k=0$：一个机器人从工厂 1 出发连走 2 步收 $1+3=4$、扣 $1$ 得 $3$；$j=3$ 时窗口已淘汰 $k=0$，胜者 $k=2$ 表示再从工厂 1 出发走 1 步收 $3$、扣 $1$，合计 $dp[3] = 3 + 2 = 5$，与样例输出一致。两条对角线在 $j=3$ 打平时任取一个，答案不受影响。

边界情况。 $p \geqslant m$ 时窗口左端钳在 $0$，允许一个机器人走完全程；窗口右端固定为 $j-1$ 保证每段长度至少为 $1$，不会出现空段；答案可能为负，取 $\max$ 的初值必须远小于任何合法收益（本题每时刻金币 $\geqslant 1$、花费 $\leqslant 100$，下界不低于 $-100m$）。

代码

prefix[c] 在一轮循环里扮演两个角色：算 value 时它还是 $P_c[k]$，加完当刻金币后变成 $P_c[j]$——两步的先后顺序不能换；queues[c] 就是对角线 $c$ 的单调队列，value 即 $V_c[k]$。

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/**
 * 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 <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int NEG = -1000000000;

int n, m, p;
int coin[1005][1005];   // coin[i][t]：第 i 条马路在第 t 个时间单位出现的金币
int cost[1005];         // 每个工厂买机器人的花费

ll prefix[1005];
deque<pair<int, ll> > queues[1005];   // (k, dp[k] - prefix - cost)
ll dp[1005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> p;
    for (int i = 0; i < n; i++)
        for (int t = 1; t <= m; t++)
            cin >> coin[i][t];
    for (int i = 0; i < n; i++) cin >> cost[i];

    for (int i = 0; i < n; i++) prefix[i] = 0;
    dp[0] = 0;
    for (int j = 1; j <= m; j++) {
        ll best = NEG;
        for (int c = 0; c < n; c++) {
            int k = j - 1;
            ll value = dp[k] - prefix[c] - cost[(k + c) % n];
            deque<pair<int, ll> >& q = queues[c];
            while (!q.empty() && q.back().second <= value) q.pop_back();
            q.push_back(make_pair(k, value));
            while (q.front().first < j - p) q.pop_front();
            prefix[c] += coin[(j + c - 1) % n][j];
            best = max(best, prefix[c] + q.front().second);
        }
        dp[j] = best;
    }
    cout << dp[m] << "\n";
    return 0;
}

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#!/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 08:13
# update_at: 2026-10-02 08:13

import sys
from collections import deque

NEG = -10**9  # dp 候选初值：净收益下界远大于此


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

    # coin[i][t]：第 i 条马路在第 t 个单位时间出现的金币（t 从 1 起）
    coin = [[0] + [next(data) for _ in range(m)] for _ in range(n)]  # n 行 × m 列
    cost = [next(data) for _ in range(n)]  # 每个工厂买机器人的花费

    # 对角线 c：时刻 t 经过的马路是 (t + c - 1) % n，一次行程恰好沿一条对角线前进。
    # prefix[c] 滚动维护该对角线的前缀和；队列里存 (k, dp[k] - 前缀和 - 购买花费)。
    prefix = [0] * n
    queues = [deque() for _ in range(n)]  # 每条对角线一个单调队列，窗口最大值 O(1)
    dp = [0] * (m + 1)  # dp[j]：前 j 个单位时间能拿到的最大净收益

    for j in range(1, m + 1):
        best = NEG
        for c in range(n):
            k = j - 1  # 上一段恰好覆盖前 k 个单位时间，本段从 k+1 时刻起步
            # 此刻 prefix[c] 正是 P_c[k]；起步工厂即 (k+1) 时刻所在的工厂
            value = dp[k] - prefix[c] - cost[(k + c) % n]
            q = queues[c]
            while q and q[-1][1] <= value:
                q.pop()  # 队尾收益不比新值大，之后永远轮不到它
            q.append((k, value))
            while q[0][0] < j - p:  # 机器人最多走 p 步，本段长度 j-k ≤ p
                q.popleft()
            prefix[c] += coin[(j + c - 1) % n][j]  # 前缀和推进到时刻 j
            best = max(best, prefix[c] + q[0][1])
        dp[j] = best

    print(dp[m])


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：$O(nm)$。外层推进 $m$ 个时刻，内层遍历 $n$ 条对角线，单调队列操作均摊 $O(1)$；恰好消掉了朴素转移里枚举段长的那一维。$n = m = 1000$ 时约 $10^6$ 轮主循环。
• 空间复杂度：$O(nm)$ 存金币矩阵（输入本身），除输入外只用 $O(n + m)$：滚动前缀和、$n$ 个单调队列与 dp 数组。

总结

• 先把「环上调度机器人」翻译成时间轴分段模型：段长不超过 $p$、段间彼此独立，一维 $dp$ 就够，不必记录机器人当前在哪个工厂。
• 行程中「马路 − 时刻」模 $n$ 不变，故收益沿对角线成段出现：对角线前缀和把行程金币和变成 $O(1)$ 区间和，还把「起点工厂」的选择一并吸收进 $c$ 的转移里。
• 转移拆成只含 $j$ 的 $P_c[j]$ 与只含 $k$ 的 $V_c[k]$ 后，内层就是长度不超过 $p$ 的滑动窗口最大值，$n$ 条对角线各配一个单调队列，总复杂度 $O(nm)$。
• 凡是「收益的两个下标一起平移」的求和，先找沿程不变量（这里是两下标之差），再沿该方向做前缀和，通常都能把内层求和消掉。