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.空间不够，因为每次状态转移时只会用到上一个状态，可以考虑用滚动数组来优化空间。代码：

#includeusing 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。