博客

题意:


一天有h个小时，有n个时间间隔。每次睡觉只睡a[i]或者a[i]-1段时间。如果在[l,r]时间内睡觉。满意度+1

解析:


设f[i][j]:表示第i段，在第j个小时睡觉

那么我们就从第i-1个段，分析。

第i-1段有两种可能要么睡a[i]时间，要么睡a[i]-1时间。

所以状态转移方程:

f[i][j]=max(f[i-1][(j-a[i]+h)%h],f[i-1][(j-(a[i]-1)+h)%h])+(l<=j&&j<=r)

#include<bits/stdc++.h>
using namespace std;
const int N=3000;
int f[N][N];
int a[N];
int n,h,l,r;
int res=0;
int main()
{
	cin>>n>>h>>l>>r;
	memset(f,-0x3f,sizeof f); //得加上这个初始化
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	f[0][0]=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<h;j++)
		{
			f[i][j]=max(f[i-1][(j-a[i]+h)%h],f[i-1][(j-(a[i]-1)+h)%h])+(l<=j&&j<=r);
		}
	}
	for(int i=0;i<h;i++) res=max(res,f[n][i]);
	cout<<res<<endl;
 }