形式化题目

$N$ 个小时排成一个环：第 $N$ 小时与第 $1$ 小时相连。要选出恰好 $B$ 个小时睡觉，选中的小时被切成若干段连续的小时，每一段的第一个小时不恢复体力，段内其余每个小时 $i$ 恢复 $U_i$ 点体力（若第 $i-1$ 个小时也睡，则第 $i$ 个小时计 $U_i$）。计划每天相同，即环上的选择固定。求恢复体力的最大值。

形式化地，求

其中 $i-1$ 取环上的前一个小时（$1-1 = N$）。$3 \leqslant N \leqslant 3830$，$2 \leqslant B < N$，$0 \leqslant U_i \leqslant 200000$。

样例 $N=5$、$B=3$、$U=[2,0,3,1,4]$：取 $S=\{4,5,1\}$，第 $4$ 小时是段首不计，收益为 $U_5 + U_1 = 4+2 = 6$。

正解

思路

朴素做法的瓶颈。 最直白的写法是枚举所有 $\binom{N}{B}$ 个睡觉方案，再花 $O(B)$ 统计体力。$\binom{3830}{1915}$ 是天文数字，完全不可行。真正的瓶颈在于状态是「选了哪些小时」这一整个集合，信息量指数级。要想压掉它，必须找出什么样的选择才决定收益。

关键观察：收益只取决于每个小时的前一个小时睡不睡。 按定义，选中的小时被切成段以后，段首不拿体力，段内其余小时拿 $U_i$；而「$i$ 是段内非首小时」等价于「$i$ 和 $i-1$ 都被选中」。于是收益可以改写成

也就是说：不需要记住整段历史，只要知道相邻两个小时各是否睡着。每个小时只有「睡着 / 清醒」两种状态，一旦确定第 $i-1$ 与第 $i$ 小时的状态，就能决定第 $i$ 小时是否贡献 $U_i$。这把指数级的状态压成了两维，天然指向 DP。

线性 DP：断环成链。 先不管环：把 $N$ 个小时看成一条普通链，第 $1$ 小时前面接一个「不睡觉的小时」，于是每个小时的收益只看左边一个小时，可以单调地从左向右扫到底。记

• $asleep[j]$：扫到当前小时为止共睡了 $j$ 个小时，且当前小时睡着的最大体力；
• $awake[j]$：同理，但当前小时清醒。

记上一轮（前一个小时结束时）的两行值为 $awake_j$（清醒）、$asleep_j$（睡着），本轮新值用撇号区分：

第一项 $awake_{j-1} \to asleep'_j$ 表示「前一小时醒着，本小时刚入睡」，不计 $U_i$；第二项 $asleep_{j-1} + U_i$ 表示「前一小时就睡着，本小时睡熟了」，计 $U_i$。每小时只需保留两个长度 $B+1$ 的数组，转移是常数级，所以整条链是 $O(NB)$。

处理环：只看第 1 小时的角色。 下标 $1 \dots N$ 里唯一「前一个小时跑到了环另一端」的只有第 $1$ 小时。所以按第 $1$ 小时在第 $N$ 小时眼里是什么身份，把所有方案分成互补的两类：

• 链 A：第 $1$ 小时不是任何一段的延续（它清醒，或者它是所在段的第一个小时）。这时它不拿 $U_1$，也不需要「第 $N$ 小时睡着」这个条件。做法是初始化 $awake[0]=0$、$asleep[1]=0$，按上面的转移扫完 $N$ 个小时，末尾在 $awake[B]$ 与 $asleep[B]$ 中取较大者。
• 链 B：第 $1$ 小时在续上一轮第 $N$ 小时的觉。既然在续睡，第 $1$ 小时必定睡着且拿 $U_1$；代价是第 $N$ 小时也必须睡着，否则这一段的「延续」就断了。做法是只把 $asleep[1]$ 初始化为 $U_1$（awake 各状态第 $1$ 小时均不可达），扫完后强制取 $asleep[B]$ 而不是两者取 max。

两类互补：任何合法方案要么第 $1$ 小时在续睡（属于链 B），要么不在（属于链 A）。链 A 把序列第 $0$ 项当成清醒，因此它把「第 $1$ 小时睡着」的方案一律当成「刚入睡」，对该方案会少算 $U_1$——但绝不会虚高；而链 B 正好精确覆盖了所有「第 $1$、$N$ 小时都睡着」的跨环方案。所以取 $\max(\text{链 A},\ \text{链 B})$ 就是答案，不必枚举断环位置。

下图用样例 $N=5,B=3,U=[2,0,3,1,4]$ 展示两条链的逐小时快照；不可达状态记「−」（表中省略了永远不可达的 $asleep[0]$）。观察 $j$ 列随时间推进的过程：asleep[3] 在链 A 的第 5 小时只到 5，而链 B 因第 1 小时就计入 $U_1$ 达到 6。

链 A：第 1 小时是新一段的第一小时或清醒（不计 $U_1$，末尾状态自由）

链 B：第 1 小时在续睡（计入 $U_1$，且强制第 $N$ 小时睡着）

链 B 最终给出 $asleep[3]=6$，正是题面的答案方案 $S=\{1,4,5\}$：第 $4$ 小时开启新的一段（不计），第 $5$ 小时续睡拿 $U_5$，即 $U_1 + 0 + U_5 = 2+0+4=6$。

注意表里第 $4$ 小时那一行 asleep[3] 是 $3$（来自方案 $\{1,3,4\}$，第 $3$ 小时开新段、第 $4$ 小时拿 $U_4=1$），到第 $5$ 小时却变成 $6$。这不是把上一条路径延长，而是 DP 在比较不同的方案：只能睡 $3$ 个小时，想在第 $5$ 小时继续睡就得放弃第 $3$ 小时。读表时要始终按「$asleep[j]$ 是前 $i$ 小时的一个最优方案」来理解，不要把一列当成同一条路径的延伸。

Python 落地：把内层循环交给 C 层。 $N \cdot B$ 最大约 $1.5\times 10^7$，纯 Python 的双层 for 会偏慢，但转移全是逐元素的 max 与加法，正好可以用切片 + map 向量化：

1
2
3
4
5# 本小时由上一个小时换来，gain 就是 U_i；NEG 表示不可达
ripe = [v + gain for v in asleep[:b]]                # 前一小时也睡着 → 本小时睡熟，计 gain
new_awake = list(map(max, awake, asleep))            # 本小时清醒，不计 gain
asleep = [NEG] + list(map(max, awake[:b], ripe))     # 本小时刚入睡，不计 gain
awake = new_awake                                    # 两行同时更新，先算完再覆盖

asleep[:b] 与 awake[:b] 配一个前置 NEG 正好实现 $j-1 \to j$ 的错位，整行 map 在 C 层一次算完。ripe 里对不可达项直接加 gain，靠 NEG 取 $-10^{30}$（远低于任何合法值）保证 $NEG + gain$ 也永远选不上。

代码

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/**
 * 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
 */
// naptime：断环成链后 DP，分「第 1 小时不续睡」与「第 1 小时续睡」两类互补求解。
#include <cstdio>
#include <vector>

typedef long long ll;

const ll NEG = -(1LL << 60); // 不可达状态

ll n, b;
std::vector<ll> awake, asleep, nxt_awake, nxt_asleep;

// 睡满 b 小时的最大恢复体力；wrapping 表示第 1 小时在续上一轮第 N 小时的觉
ll best_gain(std::vector<ll>& u, bool wrapping) {
    for (ll j = 0; j <= b; j++) {
        awake[j] = NEG;
        asleep[j] = NEG;
    }
    if (wrapping) {
        asleep[1] = u[0]; // 第 1 小时已睡熟，计入 U_1
    } else {
        awake[0] = 0;
        asleep[1] = 0; // 第 1 小时清醒，或刚入睡不计 U_1
    }
    if (b <= 0) return 0; // 题面保证 b ≥ 1，这里只做越界保护

    for (ll t = 1; t < n; t++) {
        ll gain = u[t];
        for (ll j = 0; j <= b; j++) {
            // 本小时清醒：体力不变
            nxt_awake[j] = (awake[j] > asleep[j]) ? awake[j] : asleep[j];
        }
        nxt_asleep[0] = NEG;
        for (ll j = 1; j <= b; j++) {
            ll ripe = asleep[j - 1] + gain; // 前一小时也睡着 → 睡熟了
            nxt_asleep[j] = (awake[j - 1] > ripe) ? awake[j - 1] : ripe;
        }
        for (ll j = 0; j <= b; j++) {
            awake[j] = nxt_awake[j];
            asleep[j] = nxt_asleep[j];
        }
    }

    if (wrapping) return asleep[b];
    return (awake[b] > asleep[b]) ? awake[b] : asleep[b];
}

int main() {
    if (scanf("%lld %lld", &n, &b) != 2) return 0; // 空输入安全返回
    std::vector<ll> u(n);
    for (ll i = 0; i < n; i++) scanf("%lld", &u[i]);

    awake.assign(b + 1, NEG);
    asleep.assign(b + 1, NEG);
    nxt_awake.assign(b + 1, NEG);
    nxt_asleep.assign(b + 1, NEG);

    ll a = best_gain(u, false);
    ll c = best_gain(u, true);
    printf("%lld\n", a > c ? a : c);
    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
49#!/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:20
# update_at: 2026-10-01 21:20

import sys

NEG = -10**30  # 不可达状态；体力可以全为 0，所以不能用 -1 这类普通哨兵


def best_gain(u: list[int], b: int, wrapping: bool) -> int:
    """断环成链后睡满 b 小时的最大恢复体力。

    awake[j] / asleep[j]：扫到当前小时、共睡了 j 小时，且当前小时清醒 / 睡着的最大体力。
    入睡的第一个小时不恢复体力，所以只有前一小时也睡着时本小时才累加 U_i。

    wrapping = False：第 1 小时清醒、或是它所在睡觉段的第一个小时（不计 U_1）；
    wrapping = True：第 1 小时在续上一轮第 N 小时的觉，它必定睡着且计入 U_1，
    代价是第 N 小时也必须睡着，否则「续睡」不成立。
    """
    awake = [NEG] * (b + 1)
    asleep = [NEG] * (b + 1)
    if wrapping:
        asleep[1] = u[0]                    # 第 1 小时已睡熟，计入 U_1
    else:
        awake[0], asleep[1] = 0, 0          # 第 1 小时清醒，或刚入睡不计 U_1
    for gain in u[1:]:
        # NEG 远小于任何合法值，不可达项加上 gain 仍不可能被 max 选中，无需额外保护
        ripe = [v + gain for v in asleep[:b]]             # 前一小时也睡着 → 睡熟了
        new_awake = list(map(max, awake, asleep))         # 本小时清醒，体力不变
        asleep = [NEG] + list(map(max, awake[:b], ripe))  # 本小时刚入睡，不计 gain
        awake = new_awake
    return asleep[b] if wrapping else max(awake[b], asleep[b])


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, b = next(data), next(data)
    u = [next(data) for _ in range(n)]
    # 两类互补：第 1 小时要么是所在段的第一个小时（不续睡），要么在续上一轮第 N 小时的觉。
    # 续睡那一类精确覆盖了所有跨环方案；不续睡那一类只会少算 U_1，绝不虚高，
    # 所以取 max 就是答案，不需要枚举断环位置。
    print(max(best_gain(u, b, False), best_gain(u, b, True)))


if __name__ == "__main__":
    solve()

复杂度

• 时间：两条链各扫 $N$ 个小时、每个小时处理长度 $B+1$ 的两个数组，共 $O(NB) = 1.5\times 10^7$ 次状态更新；内层用 map + 切片跑在 C 层，实测最大数据（$N=3600$、$B=2326$）约 0.95 s。
• 空间：只保留当前小时的两行数组，$O(B)$，峰值约 15 MB。

与 C++ 正解同阶（$O(NB)$ 时间、$O(B)$ 空间），Python 只是常数更大；本题限时 1 s，按 oj-python-style 约定接受 Python 可能超时，不换暴力。

总结

• 收益只由「当前小时与前一个小时是否都睡」决定，所以状态从指数级的子集压成「睡 / 醒」两维，得到 $O(NB)$ 的线性 DP。
• 环的唯一麻烦是第 $1$ 小时的前一小时在第 $N$ 小时。按第 $1$ 小时是「段首」还是「在续睡」分成两条链：链 A 不计 $U_1$ 且末尾自由，链 B 计入 $U_1$ 并强制第 $N$ 小时睡着。两类互补，取 max 即可，不必枚举断环位置。
• 实现上用两行滚动数组 + map(max, ...) 把内层循环向量化；注意 asleep[j] 的两个来源分别对应「不计 $U_i$」和「计 $U_i$」，这是全题唯一的收益规则。
• 容易写错的两处：链 B 忘记强制第 $N$ 小时睡着（样例仍然对，大数据会错）；NEG 取得不够小，加法后变成能骗过 max 的伪状态。

图示解析

这张图串起本题从建模到得到答案的主线：环上的选择只影响「段首不计体力」这一件事，因此状态压缩成睡 / 醒两维，而环的唯一难点是第 $1$ 小时的前一小时落在第 $N$ 小时。

1
2
3
4
5
6
7
8环上选 B 个小时
`- 收益只看「前一小时是否也睡」：段首不计 U_i
   `- 朴素枚举 C(N,B) 不可行 → 状态只需要「睡/醒」二维
      |- 断环成链：第 1 小时的前一小时是第 N 小时
      |  |- 链 A：第 1 小时是新段段首（不计 U_1），末尾状态自由
      |  `- 链 B：第 1 小时在续睡（计 U_1），强制第 N 小时也睡着
      `- 两条链各跑 O(NB) 滚动 DP，取最大值
         `- 两行数组 + map(max) 流水线，答案 = max(A, B)

先看「状态只需要睡 / 醒」这一步：它把指数级的子集枚举降成 $O(NB)$。再顺着两个分支看断环的处理：链 A 假设第 $1$ 小时开启新段，链 B 假设它续睡并因此强制第 $N$ 小时也睡着；两条链的并集覆盖全部合法方案，两条链各自的最优值取较大者即为答案。