codeforces 1324E. Sleeping Schedule(动态规划)
E. Sleeping Schedule(动态规划)
题目链接:
题意:
n,h,l,r,给n个时间,从0开始睡觉,每天共有 h 小时,每次睡 Ai 或者 Ai-1 的 时间,如果在l 和 r段时间入睡 那么满意度+1,问满意度最高多少?
解题思路:
动态规划问题,dp[i][j] 代表 第 i 段在第 j 小时睡觉的满意度
可以选择睡a[i]小时,可以选择睡a[i] - 1 小时,选择更优解
#include <bits/stdc++.h> using namespace std; int dp[2005][2005], a[2005]; int main(){ int n, h, l, r; cin >> n >> h >> l >> r; memset(dp,-0x3f3f3f3f,sizeof(dp)); dp[0][0] = 0; for(int i = 1; i <= n; i++){ cin >> a[i]; } for(int i = 1; i <= n; i++){ for(int j = 0; j < h; j++){ if((j + a[i]) % h >= l && (j + a[i]) % h <= r){ // 睡a[i]小时 dp[i][(j+a[i])%h] = max(dp[i][(j+a[i])%h], dp[i-1][j] + 1); } else{ dp[i][(j+a[i])%h] = max(dp[i][(j+a[i]) % h], dp[i-1][j]); } if((j + a[i] - 1) % h >= l && (j + a[i] - 1) % h <= r){ // 睡a[i]-1小时 dp[i][(j+a[i]-1)%h] = max(dp[i][(j+a[i]-1)%h], dp[i-1][j] + 1); } else{ dp[i][(j+a[i]-1)%h] = max(dp[i][(j+a[i]-1)%h], dp[i-1][j]); } } } int ans = 0; for(int i = 0; i < h; i++){ ans = max(ans, dp[n][i]); } cout << ans << endl; return 0; }
上一篇:
通过多线程提高代码的执行效率例子