头部背景图片
Decaku 's Blog |
Decaku 's Blog |

CF #627 E sleeping schedule


传送门


$ 动规,设dp[i][j]是第i次且在j时刻睡觉能获得的最大值,转移 \\
是O(1)的,只要注意不合法的状态就行了。$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define pii pair<ll,ll>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(ll i=a;i<=(ll)b;++i)
#define per(i,a,b) for(ll i=a;i>=(ll)b;--i)
#define ll long long
#define lowbit(x) ((x)&(-x))

const ll maxn=2e5+5;

int dp[2010][2010],a[2010];

int main()
{
int n,h,l,r; cin>>n>>h>>l>>r;
rep(i,1,n) cin>>a[i];
memset(dp,-1,sizeof(dp));
if(a[1]>=l&&a[1]<=r) dp[1][a[1]]=1;
else dp[1][a[1]] = 0;
if(a[1]>=l+1&&a[1]<=r+1) dp[1][a[1]-1]=1;
else dp[1][a[1]-1] = 0;
rep(i,2,n){
rep(j,0,h-1){
if(dp[i-1][j]!=-1)
{
int now = (j+a[i])%h;
if(now>=l&&now<=r) dp[i][now] = max(dp[i][now],dp[i-1][j]+1);
else dp[i][now] = max(dp[i][now],dp[i-1][j]);
}
if(dp[i-1][j]!=-1)
{
int now2 = (j+a[i]-1)%h;
if(now2>=l&&now2<=r) dp[i][now2] = max(dp[i][now2],dp[i-1][j]+1);
else dp[i][now2] = max(dp[i][now2],dp[i-1][j]);
}
}
}
int mx=0;
rep(i,0,h-1) mx=max(mx,dp[n][i]);
cout<<mx<<"\n";
}
avatar Decaku 菜菜菜