Codeforces Round #627 (Div. 3) E.Sleeping Schedule

Vova had a pretty weird sleeping schedule. There are h hours in a day. Vova will sleep exactly n times. The i-th time he will sleep exactly after ai hours from the time he woke up. You can assume that Vova woke up exactly at the beginning of this story (the initial time is 0). Each time Vova sleeps exactly one day (in other words, h hours).

Vova thinks that the i-th sleeping time is good if he starts to sleep between hours l and r inclusive.

Vova can control himself and before the i-th time can choose between two options: go to sleep after ai hours or after ai−1 hours.

Your task is to say the maximum number of good sleeping times Vova can obtain if he acts optimally.

Input

The first line of the input contains four integers n,h,l and r (1≤n≤2000,3≤h≤2000,0≤l≤r<h) — the number of times Vova goes to sleep, the number of hours in a day and the segment of the good sleeping time.

The second line of the input contains n integers a1,a2,…,an (1≤ai<h), where ai is the number of hours after which Vova goes to sleep the i-th time.

Output

Print one integer — the maximum number of good sleeping times Vova can obtain if he acts optimally.

Example

input

7 24 21 23
16 17 14 20 20 11 22

output

3

看来我还是一个 d p dp dp 小菜鸡，/(ㄒoㄒ)/~~，比赛时剩了一个小时做这题，还是不会，看了别人的代码恍然大悟，用 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示第 i i i 天减去 j j j 个小时的答案，不难得到状态转移方程：
d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − 1 ] ) dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]) dp[i][j]=max(dp[i−1][j],dp[i−1][j−1])
AC代码如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e3+5;
int n,h,l,r,a[N],dp[N][N],t,ans=0;
int main(){
    cin>>n>>h>>l>>r;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        t=t+a[i];
        for(int j=0;j<=i;j++){
            dp[i][j]=max(j?dp[i-1][j-1]:0,dp[i-1][j]);
            int tt=(t-j)%h;
            if(tt>=l && tt<=r) dp[i][j]++;
        }
    }
    for(int i=0;i<=n;i++) ans=max(ans,dp[n][i]);
    cout<<ans;
}

更多推荐

Codeforces Round #627 (Div. 3) E.Sleeping Schedule