题目
题意
-
输入 n(≤2000) h L R (0≤L≤R<h≤2000) 和长为 n 的数组 a(1≤a[i]<h)。
-
对于每个 a[i]，你可以把它减一，或者保持不变（换句话说，每个 a[i] 至多 -1 一次）。
-
定义前缀和 s[0]=a[0], s[i]=s[i-1]+a[i]。
-
如果 s[i]%h 落在闭区间 [L,R] 内，则分数加一。
-
最大化分数。
思路
- 定义dfs(i,j)为第i次睡觉的时间为j的最大分数
- 转移dfs(i,j) = max(dfs(t1,s+1) + (t1 >= l && t1 <= r),dfs(t2,s+1) + (t2 >= l && t2 <= r));
- 观察每个数字转移的时候，可以减一或者不减一，那么很明显,对于一个中间阶段有太多的重复到达的方式
- 所以记忆化搜索很容易写，也可以直接递推[https://codeforces.com/blog/entry/74714]（官方题解）
代码
const double eps = 1e-6;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int N = 2010;
int a[N];
int f[N][N];//count
int n,h,l,r;
int dfs(int t,int s)
{
if(s > n)return 0;
if(f[t][s] != -1)return f[t][s];
int t1 = (t + a[s]) % h,t2 = (t + a[s] + h - 1) % h;
return f[t][s] = max(dfs(t1,s+1) + (t1 >= l && t1 <= r),dfs(t2,s+1) + (t2 >= l && t2 <= r));
}
void solve()
{
cin >> n >> h >> l >> r;
for(int i = 1;i <= n;i ++)cin >> a[i];
memset(f,-1,sizeof f);
cout << dfs(0,1) << endl;
}