AcWing288. 休息时间(环形DP)

简介: AcWing288. 休息时间(环形DP)

原题链接

思路:

先来看只有一天的情况,dp[i][j][0]表示前i个小时休息了j个小时 并且第i个小时没休息,dp[i][j][1]表示前i个小时休息了j个小时,并且第i个小时在休息,可以得出:

dp[i][j][0]=max(dp[(i-1)][j][0],dp[(i-1)][j][1]);
dp[i][j][1]=max(dp[(i-1)][j-1][0],dp[(i-1)][j-1][1]+u[i]);

需要注意休息的第一个小时不恢复体力值。

这样的话初始化就是dp[1][0][0]=0;dp[1][1][1]=0;其余均是-inf;

最后答案就是max(dp[n][b][0],dp[n][b][1]);

题目说的是可以循环,上述情况没有包含的就是在第一个小时就已经休息就恢复体力值的情况,只需要再跑次DP,通过修改初始化状态得到这种情况即可。

要第一个小时就在恢复体力值,也就是说前一天的最后一个小时一定是已经睡觉。

初始化就是dp[1][1][1]=u[1],结果就是dp[n][b][1]。

有两个注意点:

1.第二种情况的答案不能够和dp[n][b][0]取max,因为这种状态是不合法的。

2.空间不够,因为每次状态转移时只会用到上一个状态,可以考虑用滚动数组来优化空间。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3840;
int u[3840];
int n,b;
ll dp[3][3840][2];
int main(){
    cin>>n>>b;
    for(int i=1;i<=n;i++) cin>>u[i];
    for(int i=0;i<2;i++)
        for(int j=0;j<3840;j++)
           for(int k=0;k<2;k++)
                   dp[i][j][k]=-1e18;
   /// memset(dp,-0x3f,sizeof dp);
    dp[1&1][0][0]=0;dp[1&1][1][1]=0;
    for(int i=2;i<=n;i++){
        for(int j=0;j<=b;j++){
            dp[i&1][j][0]=max(dp[(i-1)&1][j][0],dp[(i-1)&1][j][1]);
            if(j>=1) dp[i&1][j][1]=max(dp[(i-1)&1][j-1][0],dp[(i-1)&1][j-1][1]+u[i]);///休息的第一个小时不恢复体力值
        }
    }
    ll res=max(dp[n&1][b][0],dp[n&1][b][1]);
    ///memset(dp,-0x3f,sizeof dp);
    for(int i=0;i<2;i++)
        for(int j=0;j<3840;j++)
           for(int k=0;k<2;k++)
                   dp[i][j][k]=-1e18;
    dp[1&1][1][1]=u[1];
    for(int i=2;i<=n;i++){
        for(int j=0;j<=b;j++){
            dp[i&1][j][0]=max(dp[(i-1)&1][j][0],dp[(i-1)&1][j][1]);
            if(j>=1) dp[i&1][j][1]=max(dp[(i-1)&1][j-1][0],dp[(i-1)&1][j-1][1]+u[i]);///休息的第一个小时不恢复体力值
        }
    }
    res=max(res,dp[n&1][b][1]);
    printf("%lld\n",res);
    return 0;
}
目录
相关文章
|
6月前
[leetcode ~dp ]279. 完全平方数
[leetcode ~dp ]279. 完全平方数
|
6月前
|
机器学习/深度学习
【每日一题Day271】LC918环形子数组的最大和 | 分类讨论 + dp
【每日一题Day271】LC918环形子数组的最大和 | 分类讨论 + dp
46 0
【每日一题Day271】LC918环形子数组的最大和 | 分类讨论 + dp
|
人工智能
动态规划(DP)——线性DP
动态规划(DP)——线性DP
LeetCode剑指 Offer 49. 丑数(dp/打表)
LeetCode剑指 Offer 49. 丑数(dp/打表)
(闫氏dp分析法)AcWing 2. 01背包问题
(闫氏dp分析法)AcWing 2. 01背包问题
60 0
|
人工智能
洛谷P1115-最大子段和(DP-最大子段和)
洛谷P1115-最大子段和(DP-最大子段和)
洛谷P1115-最大子段和(DP-最大子段和)