题目详解

问题描述

Vova 初始时刻为 $0$，一天有 $h$ 小时。他总共要睡 $n$ 次，第 $i$ 次他可以选择在醒来后经过 $a_i$ 小时或者 $a_i-1$ 小时开始睡觉（每次睡觉恰好持续 $h$ 小时，因此我们只关心开始时刻模 $h$ 的余数）。如果开始时刻模 $h$ 落在区间 $[l, r]$ 内，则这次睡眠是“好的”。求最多能得到多少次好的睡眠。

问题分析

设第 $i$ 次睡眠前的时间为 $t_{i-1}$（$t_0 = 0$），第 $i$ 次的选择为 $d_i \in \{0, 1\}$，其中 $d_i = 0$ 表示加 $a_i$，$d_i = 1$ 表示加 $a_i-1$。那么第 $i$ 次睡眠的开始时刻为：

我们只关心 $t_i \bmod h$ 是否属于 $[l, r]$。

令前缀和 $S_i = \sum_{k=1}^i a_k$，则：

因此 $t_i \bmod h = (S_i - D_i) \bmod h$，其中 $D_i = \sum_{k=1}^i d_k$ 表示前 $i$ 次中选择“减 $1$”的总次数。

动态规划解法

我们可以按照次数依次决策，用 DP 记录当前已使用的“减 $1$”次数以及获得的好睡眠次数。

状态定义

设 $dp[i][j]$ 表示考虑了前 $i$ 次睡眠，恰好使用了 $j$ 次“减 $1$”时，能获得的最大好睡眠次数。
其中 $0 \le i \le n$，$0 \le j \le i$（因为最多 $i$ 次减 $1$）。

初始状态

$dp[0][0] = 0$，表示还没开始睡觉，没有减 $1$ 次数，好睡眠数为 $0$。其余状态初始化为 $-\infty$（表示不可达）。

状态转移

对于第 $i$ 次（$1 \le i \le n$），设前缀和 $sum = \sum_{k=1}^i a_k$。
已知前 $i-1$ 次的状态 $dp[i-1][j]$，现在考虑第 $i$ 次的选择：

• 不减 $1$（即 $d_i = 0$）：那么新的减 $1$ 总次数仍为 $j$，新的开始时刻为 $(sum - j) \bmod h$。若该时刻落在 $[l, r]$ 内，则这次睡眠好，贡献 $1$，否则贡献 $0$。
  转移方程：

  $$dp[i][j] = \max(dp[i][j],\; dp[i-1][j] + \big[ (sum - j) \bmod h \in [l, r] \big]) $$

• 减 $1$（即 $d_i = 1$）：此时减 $1$ 总次数变为 $j+1$，开始时刻为 $(sum - (j+1)) \bmod h$。
  转移方程：

  $$dp[i][j+1] = \max(dp[i][j+1],\; dp[i-1][j] + \big[ (sum - j - 1) \bmod h \in [l, r] \big]) $$

答案

最终答案为：

复杂度

状态数 $O(n^2)$，转移 $O(1)$，总复杂度 $O(n^2)$，在 $n \le 2000$ 时可行。

代码实现（标程风格）

#include <bits/stdc++.h>
using namespace std;

bool in(int x, int l, int r) {
    return l <= x && x <= r;
}

int main() {
    int n, h, l, r;
    cin >> n >> h >> l >> r;
    vector<int> a(n);
    for (auto &it : a) cin >> it;
    
    // dp[i][j]：前i次，用了j次减1，最大好睡眠数
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MIN));
    dp[0][0] = 0;
    
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        sum += a[i];
        for (int j = 0; j <= i; ++j) {
            if (dp[i][j] == INT_MIN) continue;
            // 选择不加1（即不减1）
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + in((sum - j) % h, l, r));
            // 选择减1
            dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + in((sum - j - 1) % h, l, r));
        }
    }
    
    cout << *max_element(dp[n].begin(), dp[n].end()) << endl;
    return 0;
}

示例验证

输入：

7 24 21 23
16 17 14 20 20 11 22

运行过程（部分）：

• 初始 $sum=0$，$dp[0][0]=0$。
• 第 $1$ 次：$sum=16$。
  从 $j=0$：
  • 不减1：时刻 $(16-0)\%24=16$，不在 $[21,23]$，$dp[1][0]=0$。
  • 减1：时刻 $(16-1)\%24=15$，不在区间，$dp[1][1]=0$。
• …最终 $dp[7][j]$ 的最大值为 $3$，输出 $3$，与题目一致。

总结

本题的关键是将选择“减 $1$”的次数作为 DP 的第二维，利用前缀和与减 $1$ 次数的线性关系得到当前时刻，从而判断是否产生好睡眠。该 DP 设计巧妙，时间复杂度 $O(n^2)$ 足以通过本题。