题目：传送门
题意：略
思路：显然是DAG模型，类似于01背包，但顺序固定，不得跳过。
状态转移方程：dp(i,j) = max （ dp (i-1,j-a[i]+1) , dp(i-1,j-a[i]) ） + l<=j&&j<=r ; 其中dp(i,j) 表示 第i次在j时刻睡觉，a[i] 指在 经过a[i]时或a[i]-1时 睡觉, j-a[i] 可能为负，注意取模。其中有许多状态不能达到，对于这些不可达的状态用-1表示（只要表示对了就行）。
#include<bits/stdc++.h> #pragma GCC optimize(2) using namespace std; typedef long long LL; typedef pair<int,int> pii; typedef pair<double,double> pdd; const int N=4e3+5; const int inf=0x3f3f3f3f; const int mod=1e9+7; const double eps=1e-9; const long double pi=acos(-1.0L); #define ls (i<<1) #define rs (i<<1|1) #define fi first #define se second #define pb push_back #define mk make_pair #define mem(a,b) memset(a,b,sizeof(a)) LL read() { LL x=0,t=1; char ch; while(!isdigit(ch=getchar())) if(ch=='-') t=-1; while(isdigit(ch)){ x=10*x+ch-'0'; ch=getchar(); } return x*t; } int a[N],dp[N][N]; int main() { int n=read(),h=read(),l=read(),r=read(); for(int i=1;i<=n;i++) a[i]=read(); mem(dp,-1); dp[0][0]=0; for(int i=1;i<=n;i++) { for(int j=0;j<h;j++) { int t1=(j-a[i]+1+h)%h,t2=(j-a[i]+h)%h; if(dp[i-1][t1]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][t1]+(l<=j&&j<=r)); if(dp[i-1][t2]!=-1) dp[i][j]=max(dp[i][j],dp[i-1][t2]+(l<=j&&j<=r)); } } int ans=0; for(int i=0;i<h;i++) ans=max(ans,dp[n][i]); printf("%d ",ans); return 0; }