CodeForces-1324E Sleeping Schedule

传送门：CodeForces-1324E

题目描述

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 $a_i$ hours from the time he woke up. You can assume that Vova woke up exactly at the beginning of this story . Each time Vova sleeps exactly one day

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 $a_i$ hours or after $a_i−1$ hours.

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

输入描述

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 $a_1,a_2,…,a_n$ $(1≤a_i<h)$, where $a_i$ is the number of hours after which Vova goes to sleep the $i$-th time.

输出描述

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

思路分析

$dp[i][j]$表示对于前$i$个时间，有$j$个选择了$-1$的最多good次数
转移就很明显了，用前缀和预处理一下

样例输入

7 24 21 23
16 17 14 20 20 11 22

样例输出

3

AC代码

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N=1e5+10;

int dp[2020][2020];
int s[N];
int n,d,l,r;

int judge(int x) {
    x%=d;
    if(x>=l&&x<=r) return 1;
    else return 0;
}

int main() {
    IOS;
#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif


    cin>>n>>d>>l>>r;
    for(int i=1; i<=n; i++) {
        int x;
        cin>>x;
        s[i]=s[i-1]+x;
    }
    int ans=-INF;
    for(int i=1; i<=n; i++)
        for(int j=0; j<=i; j++)
            dp[i][j]=max(dp[i-1][j-1!=-1?j-1:0],dp[i-1][j])+judge(s[i]-j);

    for(int i=0; i<=n; i++)
        ans=max(ans,dp[n][i]);
    cout<<ans<<endl;




    return 0;
}