Sleeping Schedule
思路：一個睡眠時間和下一個睡眠時間的情況是傳遞關系，所以我們需要記錄每一層的資訊，一天的時間h可以壓縮資訊，dp[i][j]可以表示在第i個睡眠階段，第j時刻“good sleep”的次數，
如果dp[i - 1][j]是合法情況，即狀態轉移程序中，出現過這個程序，則分兩種情況轉移：
dp[i][(j + ai) % h] = max(dp[i][(j + ai) % h], dp[i - 1][j] + is_good_sleep?);
dp[i][(j + ai - 1) % h] = max(dp[i][(j + ai - 1) % h], dp[i - 1][j] + is_good_sleep?);
1 #include <iostream> 2 #include <deque> 3 #include <algorithm> 4 #include <stack> 5 #include <vector> 6 #include <cstring> 7 8 using namespace std; 9 10 const int N = 2e3 + 10; 11 int dp[N][N]; 12 int n, h, l, r; 13 14 inline int add(int x){ 15 return x >= l && x <= r; 16 } 17 18 void solve(){ 19 20 cin >> n >> h >> l >> r; 21 int ai; 22 memset(dp, -1, sizeof(dp)); 23 //cout << dp[0][0] << endl; 24 dp[0][0] = 0; 25 for(int i = 1; i <= n; ++i){ 26 cin >> ai; 27 for(int j = 0; j < h; ++j){ 28 if(dp[i - 1][j] != -1){ 29 dp[i][(j + ai) % h] = 30 max(dp[i][(j + ai) % h], dp[i - 1][j] + add((j + ai) % h)); 31 32 dp[i][(j + ai - 1) % h] = 33 max(dp[i][(j + ai - 1) % h], dp[i - 1][j] + add((j + ai - 1) % h)); 34 } 35 } 36 } 37 int Max_tot = -1; 38 for(int i = 0; i < h; ++i){ 39 Max_tot = max(Max_tot, dp[n][i]); 40 } 41 cout << Max_tot << endl; 42 } 43 44 int main(){ 45 46 ios::sync_with_stdio(false); 47 cin.tie(0); 48 cout.tie(0); 49 solve(); 50 51 return 0; 52 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/60076.html
標籤：其他
上一篇：LeetCode刷題日記
下一篇：演算法--排序基礎