CodeForces 1324E Sleeping Schedule

题意

$Vova$ 有一个睡眠时间表，一天有 $h$ 小时， $Vova$ 会睡 $n$ 次觉，一次睡一天，在第 $i-1$ 次睡醒后， $Vova$ 在 $a_i$ 或 $a_i-1$ 个小时候可以再次入睡，一开始时间为第 $0$ 时（可以视作 $Vova$ 刚醒）， $Vova$ 在 $[l,r]$ 区间时睡觉会睡得舒服，问 $Vova$ 最多可以睡几次舒服觉

分析

发现第 $i$ 次睡眠的时间是由第 $i-1$ 次睡眠时间决定的，一个显然的转移，因此这道题采用 $DP$

首先我们可以设第 $0$ 次睡眠时， $Vova$ 是在第 $0$ 时刻睡的

假设 $Vova$ 在第 $i-1$ 次睡眠时在第 $j$ 时刻，那么第 $i$ 次 $Vova$ 可以在第 $(j+a_i)\%h$ 时刻或者在第 $(j+a_i-1)\%h$ 时刻睡觉，我们可以记录一个 $vis[i][j]$ 表示 $Vova$ 在第 $i$ 次睡眠时在第 $j$ 时刻可以睡

而如果 $(j+a_i)\%h$ 在 $[l,r]$ 区间内，则第 $i$ 次睡眠在第 $(j+a_i)\%h$ 时刻的答案数为第 $i-1$ 次睡眠时 $j$ 时刻的答案数加一，因为有多种方案使得 $Vova$ 能在第 $i-1$ 次睡眠时在第 $j$ 时刻，因此取最大值，可以记录 $dp[i][j]$ 表示在第 $i$ 次睡眠时在第 $j$ 时刻的答案， $dp[i][(j+a_i)\%h]=max(dp[i-1][j]+1,dp[i][(j+a_i)\%h])$

如果 $(j+a_i)\%h$ 不在 $[l,r]$ 区间内，则 $dp[i][(j+a_i)\%h]=max(dp[i-1][j],dp[i][(j+a_i)\%h])$

答案可以在每次更新 $dp[i][j]$ 时更新

$(j+a_i-1)\%h$ 同理

这题不卡空间，可以不使用滚动数组

#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
using namespace std;
const int maxn = (ll) 3e5 + 5;
const int mod = 1000000007;
const int inf = 0x3f3f3f3f;
int dp[2005][2005];
bool vis[2005][2005];
int ans;

signed main() {
    start;
    int n, h, l, r;
    cin >> n >> h >> l >> r;
    vis[0][0] = true;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        for (int j = 0; j < 2000; ++j) {
            if (vis[i - 1][j]) {
                int t = (j + x) % h;
                vis[i][t] = true;
                if (t >= l && t <= r)
                    dp[i][t] = max(dp[i][t], dp[i - 1][j] + 1);
                else
                    dp[i][t] = max(dp[i][t], dp[i - 1][j]);
                ans = max(ans, dp[i][t]);
                t = (j + x - 1) % h;
                vis[i][t] = true;
                if (t >= l && t <= r)
                    dp[i][t] = max(dp[i][t], dp[i - 1][j] + 1);
                else
                    dp[i][t] = max(dp[i][t], dp[i - 1][j]);
                ans = max(ans, dp[i][t]);
            }
        }
    }
    cout << ans;
    return 0;
}