传送门

  • 题目：
  • 思路：
    h用处不大，因为上次睡的时间和下次醒的时间是一样的，每次都面临两种选择。
    d p [ i ] [ j ] dp[i][j] dp[i][j]表示前 i i i次选择 j j j次“ a i − 1 a_i-1 ai​−1”这种方案能够获得的最大good sleeping数（ 0 ≤ j ≤ I 0≤j≤I 0≤j≤I）
    s u m [ i ] = ∑ k = 1 i a k sum[i]=\sum_{k=1}^i a_k sum[i]=∑k=1i​ak​
    d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] + ∣ ( s u m [ i ] − j ) % h ∈ [ l , r ] ∣ , d p [ i − 1 ] [ j − 1 ] + ∣ ( s u m [ i ] − j ) % h ∈ [ l , r ] ∣ ) dp[i][j]=max(dp[i-1][j]+|(sum[i]-j)\%h\in[l,r]|, dp[i-1][j-1]+|(sum[i]-j)\%h\in[l,r]|) dp[i][j]=max(dp[i−1][j]+∣(sum[i]−j)%h∈[l,r]∣,dp[i−1][j−1]+∣(sum[i]−j)%h∈[l,r]∣)
    d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − 1 ] ) + ∣ ( s u m [ i ] − j ) % h ∈ [ l , r ] ∣ dp[i][j]=max(dp[i-1][j], dp[i-1][j-1])+|(sum[i]-j)\%h\in[l,r]| dp[i][j]=max(dp[i−1][j],dp[i−1][j−1])+∣(sum[i]−j)%h∈[l,r]∣
  • ac代码： 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2010;
const ll mod = 998244353;
int n, h, l, r, x;
int dp[maxn][maxn], sum[maxn];
bool check(int x)
{
    x%=h;
    return l<=x && x<=r;
}
int main()
{
    //freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    scanf("%d %d %d %d", &n, &h, &l, &r);
    for(int i = 1; i <= n; i++) scanf("%d", &x), sum[i]=sum[i-1]+x;
    for(int i = 1; i <= n; i++)
    {
        dp[i][0] = dp[i-1][0]+check(sum[i]);
        for(int j = 1; j <= i; j++)
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1])+check(sum[i]-j);
    }
    int ans = 0;
    for(int i = 0; i <= n; i++) ans = max(ans, dp[n][i]);
    printf("%d\n", ans);
    return 0;
}