或許更好的閱讀體驗

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）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。