E. Sleeping Schedule 【记忆化搜索】
思路
暴搜 + 记忆化即可。
题意
小v 在第 i 次醒来后（最开始是醒的）的第 a[i] 小时 或者 a[i] - 1 小时睡觉，每次睡一天（这个一天的定义是 h 时）。
令 小v 睡觉的时间点为 x ，如果 L ≤ X ≤ R，就睡得好。
问最多能睡得好多少次。
CODE
#include < bits/stdc++.h >
#define dbg ( x ) cout << #x << " = " << x << endl
#define eps 1e - 8
#define pi acos ( - 1.0 )
using namespace std ;
typedef long long LL ;
const int inf = 0x3f3f3f3f ;
template < class T > inline void read ( T & res )
{
char c ;T flag = 1 ;
while ((c = getchar ()) < ' 0 ' ||c > ' 9 ' ) if (c == ' - ' )flag =- 1 ;res =c - ' 0 ' ;
while ((c = getchar ()) >= ' 0 ' &&c <= ' 9 ' )res =res * 10 +c - ' 0 ' ;res *=flag ;
}
namespace _buff {
const size_t BUFF = 1 << 19 ;
char ibuf [BUFF ], *ib = ibuf , *ie = ibuf ;
char getc () {
if (ib == ie ) {
ib = ibuf ;
ie = ibuf + fread (ibuf , 1 , BUFF , stdin );
}
return ib == ie ? - 1 : *ib ++ ;
}
}
int qread () {
using namespace _buff ;
int ret = 0 ;
bool pos = true ;
char c = getc ();
for (; (c < ' 0 ' || c > ' 9 ' ) && c != ' - ' ; c = getc ()) {
assert ( ~c );
}
if (c == ' - ' ) {
pos = false ;
c = getc ();
}
for (; c >= ' 0 ' && c <= ' 9 ' ; c = getc ()) {
ret = (ret << 3 ) + (ret << 1 ) + (c ^ 48 );
}
return pos ? ret : -ret ;
}
const int maxn = 4007 ;
int a [maxn ];
int n ,h ,l ,r ;
int f [maxn ][maxn ];
int dfs ( int x , int now ) {
//dbg(now);
if (x > n ) {
return 0 ;
}
if (f [x ][now ] != - 1 ) {
return f [x ][now ];
}
int temp = (now + a [x ]) % h ;
int res = 0 ;
int q = 0 ;
if (temp <= r && temp >= l ) {
q ++ ;
}
int res1 = q + dfs (x + 1 , temp );
q = 0 ;
temp = (now + a [x ] - 1 ) % h ;
if (temp <= r && temp >= l ) {
q ++ ;
}
int res2 = q + dfs (x + 1 , temp );
res = max (res1 , res2 );
f [x ][now ] = res ;
return res ;
}
int main ()
{
scanf ( "%d %d %d %d " , &n , &h , &l , &r );
for ( int i = 1 ; i <= n ; ++i ) {
read ( a [i ]);
}
memset (f , - 1 , sizeof (f ));
printf ( "%d \n" , dfs ( 1 , 0 ));
return 0 ;
}
查看19道真题和解析