E. Sleeping Schedule - 题解

比赛与标签

比赛: Codeforces Round 627 (Div. 3) 标签: dp, implementation 难度: *1700

题目大意喵~

各位好呀，今天我们来解决一个关于睡觉时间规划的有趣问题，喵~

是这样的，有一位名叫 Vova 的朋友，他有 n 次睡眠计划。这个世界的一天有 h 个小时。Vova 从时间 0 开始醒着，他的第 i 次睡眠会发生在他醒来后的 a_i 个小时。

但是呢，Vova 有一点小小的自控能力！对于第 i 次睡眠，他可以选择在 a_i 小时后入睡，也可以选择提前一点点，在 a_i - 1 小时后入睡。

Vova 认为，如果一次睡眠的开始时间 t 恰好在 [l, r] 这个时间段内（闭区间哦），那么这次睡眠就是一次“良好”的睡眠。

我们的任务就是帮助 Vova 做出聪明的选择，让他能够获得的“良好”睡眠次数最多！我们需要输出这个最大次数，的说。

解题思路喵~

这个问题呀，每一步都有两种选择，而且当前的选择会影响到未来的时间，最终要求一个最优解（最大次数）。这闻起来就像是动态规划（DP）的味道呢，喵！

让我们一步一步来分析吧！

1. 状态定义

我们需要记录什么信息才能做出下一步的决策呢？在考虑第 i 次睡眠时，我们最关心的是：

我们已经考虑了多少次睡眠了？（也就是 i）
在做出第 i 次睡眠决策之前，当前的时间点是多少？（一个 0 到 h-1 的值）

结合这两点，我们可以定义一个二维的 DP 状态： dp[i][j] 表示：在完成第 i 次睡眠后，时间恰好是 j 点时，能够获得的最大“良好”睡眠次数。

2. 状态转移

想一想，dp[i][j] 的值可以从哪里来呢？它肯定是从第 i-1 次睡眠结束后的某个状态转移过来的。假设第 i-1 次睡眠结束后，时间是 t 点，此时我们已经获得了 dp[i-1][t] 次良好睡眠。

现在我们要进行第 i 次睡眠了（这次的间隔是 a_i），我们有两种选择：

选择 1：等待 a_i - 1 小时 新的时间点将是 new_t1 = (t + a_i - 1) % h。这次睡眠是否良好，取决于 new_t1 是否在 [l, r] 区间内。所以，通过这个选择，我们可以更新 dp[i][new_t1] 的值。
选择 2：等待 a_i 小时 新的时间点将是 new_t2 = (t + a_i) % h。同样，这次睡眠是否良好，取决于 new_t2 是否在 [l, r] 区间内。通过这个选择，我们可以更新 dp[i][new_t2] 的值。

因为我们要求的是最大值，所以状态转移方程就是：对于所有可能的上一个时间点 t (从 0 到 h-1)：

new_t1 = (t + a_i - 1) % his_good1 = (l <= new_t1 <= r) ? 1 : 0dp[i][new_t1] = max(dp[i][new_t1], dp[i-1][t] + is_good1)
new_t2 = (t + a_i) % his_good2 = (l <= new_t2 <= r) ? 1 : 0dp[i][new_t2] = max(dp[i][new_t2], dp[i-1][t] + is_good2)

3. 初始化与边界条件

初始状态：在 Vova 进行任何睡眠之前（可以看作第 0 次睡眠后），他位于时间 0，良好睡眠次数当然也是 0。所以 dp[0][0] = 0。
不可达状态：对于其他所有 dp[0][j] (当 j > 0 时)，都是不可能达到的状态。为了区分它们，我们可以把 dp 数组所有元素初始化为一个特殊值，比如 -1，表示“这个状态还从未达到过”，的说。

4. 空间优化！

敏锐的你可能已经发现了，计算第 i 行的 dp 值，我们只需要第 i-1 行的信息，喵~ 这意味着我们可以用“滚动数组”的思想来优化空间！

我们不需要一个 n * h 的大二维数组，只需要两个大小为 h 的一维数组就够了：一个叫 dp，存上一轮的结果；另一个叫 next_dp，存当前这轮计算出的新结果。每轮计算结束后，用 next_dp 覆盖掉 dp 就好啦！这样空间复杂度就从 O(n*h) 降到了 O(h)，是不是很棒呐！

5. 最终答案

在处理完所有 n 次睡眠后，Vova 可能在 0 到 h-1 的任何一个时间点结束。我们最终的答案，就是 dp 数组里所有值的最大值！

代码实现喵~

下面就是根据这个思路写出的AC代码啦，我已经加上了详细的注释，希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// Function to solve the problem
void solve() {
    int n, h, l, r;
    std::cin >> n >> h >> l >> r;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // dp[t] 表示在某一轮结束后，时间点为 t 时的最大良好睡眠次数，喵~
    // 我们用 -1 来表示一个从未达到过的状态。
    std::vector<int> dp(h, -1);
    
    // 基础情况：在任何睡眠开始前，我们在时间 0，有 0 次良好睡眠。
    // 这是我们整个DP的起点哦！
    dp[0] = 0;

    // 遍历 Vova 的每一次睡眠计划
    for (int i = 0; i < n; ++i) {
        // 准备一个 next_dp 数组来存放这一轮计算的结果，防止状态污染
        std::vector<int> next_dp(h, -1);
        
        // 遍历上一轮所有可能的时间点 t
        for (int t = 0; t < h; ++t) {
            // 如果上一个状态 dp[t] 是不可达的，那就没法从这里出发，直接跳过，喵！
            if (dp[t] == -1) {
                continue;
            }

            // Vova 对第 i 次睡眠有两个选择
            // 选择 1: 等待 a[i] - 1 小时后入睡
            int time1 = (t + a[i] - 1) % h;
            int is_good1 = (time1 >= l && time1 <= r); // 判断这次睡眠好不好
            // 更新新状态 time1 的最大良好睡眠次数
            next_dp[time1] = std::max(next_dp[time1], dp[t] + is_good1);

            // 选择 2: 等待 a[i] 小时后入睡
            int time2 = (t + a[i]) % h;
            int is_good2 = (time2 >= l && time2 <= r); // 判断这次睡眠好不好
            // 更新新状态 time2 的最大良好睡眠次数
            next_dp[time2] = std::max(next_dp[time2], dp[t] + is_good2);
        }
        
        // 当前轮次计算完毕，用 next_dp 的结果更新 dp，准备下一轮迭代！
        dp = std::move(next_dp);
    }

    // 经过 n 次睡眠后，我们可能在任何一个时间点结束。
    // 最终答案就是所有可能结束时间点对应的良好睡眠次数中的最大值。
    int max_good_sleeps = 0;
    for (int i = 0; i < h; ++i) {
        max_good_sleeps = std::max(max_good_sleeps, dp[i]);
    }

    std::cout << max_good_sleeps << std::endl;
}

int main() {
    // 加速一下输入输出，让程序跑得飞快~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    solve();

    return 0;
}

复杂度分析的说

时间复杂度: O(n * h) 的说。我们有一个外层循环 n 次（对应 n 次睡眠），内层循环 h 次（对应一天中的所有小时）。所以总的计算量是 n 和 h 的乘积。对于这道题的范围 (n, h <= 2000)，这是完全可以接受的！
空间复杂度: O(h) 的说。因为我们使用了滚动数组的优化，只需要两个大小为 h 的数组来存储DP状态，所以空间开销只和 h 有关，非常节省内存，喵~

知识点与总结喵~

这道题是一道非常经典的线性DP问题，通过它我们可以复习和掌握几个重要的知识点呐：

动态规划思想: 识别问题的最优子结构和重叠子问题，从而设计出状态和状态转移方程。本题的“第 i 步的最优解依赖于第 i-1 步的各种可能解”是DP的典型特征。
状态定义: 合理地定义 dp 数组的含义是解决DP问题的关键。dp[i][t] 的定义清晰地捕捉了问题的核心要素。
空间优化（滚动数组）: 在DP问题中，如果当前状态只依赖于前一个或前几个状态，一定要考虑使用滚动数组来优化空间。这在 n 特别大而状态维度较小时尤其有用！
模运算: 处理与周期、循环相关的问题时（比如一天的时间），千万不要忘记使用取模运算（% h），不然时间就会跑到第二天去啦！
初始化: DP的边界条件和初始状态的设定至关重要。使用特殊值（如-1）标记不可达状态是一个非常实用的技巧。

希望这篇题解能让你对DP有更深的理解！继续加油，你超棒的，喵~！

E. Sleeping Schedule - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路喵~ ​

1. 状态定义 ​

2. 状态转移 ​

3. 初始化与边界条件 ​

4. 空间优化！ ​

5. 最终答案 ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结喵~ ​