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月前
流(树形dp,换根dp)
流(树形dp,换根dp)
30 0
|
6月前
daimayuan(代码源oj)最长路径(树形dp,无向树换根dp)
daimayuan(代码源oj)最长路径(树形dp,无向树换根dp)
126 0
|
6月前
树形dp常见类型——换根dp
树形dp常见类型——换根dp
|
3月前
|
算法
LeetCode第64题最小路径和
LeetCode第64题"最小路径和"的解题方法,运用动态规划思想,通过构建一个dp数组来记录到达每个点的最小路径和,从而高效求解。
LeetCode第64题最小路径和
|
6月前
|
机器学习/深度学习
【每日一题Day271】LC918环形子数组的最大和 | 分类讨论 + dp
【每日一题Day271】LC918环形子数组的最大和 | 分类讨论 + dp
54 0
【每日一题Day271】LC918环形子数组的最大和 | 分类讨论 + dp
|
6月前
leetcode-64:最小路径和
leetcode-64:最小路径和
39 0
|
人工智能
动态规划(DP)——线性DP
动态规划(DP)——线性DP