【CF1324E】Sleeping Schedule（dp）

传送门

• 题目：
  
• 思路：
  h用处不大，因为上次睡的时间和下次醒的时间是一样的，每次都面临两种选择。
  $dp\left[i\right]\left[j\right]$dp[i][j]表示前 $i$i次选择 $j$j次“ $a_i-1$ai​−1”这种方案能够获得的最大good sleeping数（ $0\le j\le I$0≤j≤I）
  $sum\left[i\right]={\sum }_{k=1}^i{a}_k$sum[i]=∑k=1i​ak​
  $dp\left[i\right]\left[j\right]=max\left(dp\right[i-1\left]\right[j]+\mid (sum\left[i\right]-j)\%h\in [l,r]\mid ,dp[i-1\left]\right[j-1]+\mid (sum\left[i\right]-j)\%h\in [l,r\left]\mid \right)$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]∣)
  $dp\left[i\right]\left[j\right]=max\left(dp\right[i-1\left]\right[j],dp[i-1\left]\right[j-1\left]\right)+\mid \left(sum\right[i]-j)\%h\in [l,r]\mid$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;
}