E：Sleeping Schedule（DP）

或许更好的阅读体验

Sleeping Schedule

思路

这道题读题就感觉像时$DP$，读完题后更加坚定了，这是一道$DP$题目。

我们考虑状态转移方程，$dp[i][j]$表示在第$i$次入睡时间是$j$的时候的时间最优值，所以显然有我们的状态转移方程就是

$dp[i][(j+a[i])\%n]=max((dp[i][j+a[i])\%n),dp[i-1][j]+1$，这里的j枚举的是上一次入睡的时间，因为是睡一天嘛，所以下一次睡觉的时间就是$(j+a[i])\%b$

当然这里并没有考虑完备，因为我们还有一个时间时是$(j+a[i]-1)\%n$，但是转移过程跟上面是一样的，这里就不多列式子了。

接下来我在代码里说一些我wa过得坑点。

代码

#include <bits/stdc++.h>using namespace std;typedef long long ll;inline ll read() {ll f = 1, x = 0;char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();} while(c >= '0' && c <= '9') {x = (x << 1) + (x << 3) + (c ^ 48);c = getchar();}return f * x; }const int N = 2e3 + 10;int dp[N][N], a[N], n, h, l, r;int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);// ios::sync_with_stdio(false);n = read(), h = read(), l = read(), r = read();for(int i = 1; i <= n; i++)a[i] = read();memset(dp, -1, sizeof dp);//初始化，dp[0][0] = 0;//只有这个状态是合理的，所以初始化为0.for(int i = 1; i <= n; i++)for(int j = 0; j < h; j++) {//昨天是在j时入睡的，if(dp[i - 1][j] < 0) continue;//只能从上面一个合理的状态转移过来，所以上一个状态一定要满足是>= 0的，if((a[i] + j) % h >= l && (a[i] + j) % h <= r)//隔a[i]dp[i][(a[i] + j) % h] = max(dp[i][(a[i] + j) % h], dp[i - 1][j] + 1);elsedp[i][(a[i] + j) % h] = max(dp[i][(a[i] + j) % h], dp[i - 1][j]);if((a[i] + j - 1) % h >= l && (a[i] + j - 1) % h <= r)//隔a[i] - 1dp[i][(a[i] + j - 1) % h] = max(dp[i][(a[i] + j - 1) % h], dp[i - 1][j] + 1);elsedp[i][(a[i] + j - 1) % h] = max(dp[i][(a[i] + j - 1) % h], dp[i - 1][j]);}int ans = 0;for(int i = 0; i < h; i++)//从0 ~ h - 1枚举，并不是1 ~ n，这点一定注意。ans = max(ans, dp[n][i]);printf("%d\n", ans);return 0; }

总结

以上是生活随笔为你收集整理的E：Sleeping Schedule（DP）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。