题目
题意
- 输入 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));
- 观察每个数字转移的时候，可以减一或者不减一，那么很明显,对于一个中间阶段有太多的重复到达的方式
- 所以记忆化搜索很容易写，也可以直接递推[codeforces.com/blog/entry/…
代码
ini
复制代码
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; }
