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;
}