poj 3661 Running (区间dp)

poj 3661题目链接

题意:锻炼,一共n分钟,每分钟可以选择跑步或者休息,第i分钟跑步可以跑d[i]米,并增加一点疲劳度,如果选择休息,那么每分钟减少1点疲劳值。一旦开始休息,必须休息到疲劳值为0才能再次开始跑步。疲劳值不能超过m.第n分钟的时候疲劳值必须为0,否则之后会感觉身体被掏空。问n分钟最远多多远。

思路:

我能想到的:

  • dp[i][j]表示第i分钟疲劳度为j的时候能跑的最远距离
  • 初始化dp为0.
  • 最后的答案为dp[n][0]
  • 如果第i分钟跑步,转移方程为dp[i][j] = max(dp[i][j],dp[i-1][j-1]+d[i]);

我想错了的:

  • 休息的时候的转移方程应该是第i天刚好休息好时:dp[i][0]=max(dp[i-j][j],dp[i][0]) 而不是开始休息
  • 由于是第i天休息好时的状态,那么开始休息的时间是固定的(第i-j天),只进行一个转移,而不会影响中间的那些天

我想的不够好的:

  • 考虑到了可能最后几天为了疲劳度为0干脆就不跑,我的做法是取了所有的dp[i][0]的最大值。但是更好的做法似乎是dp[i][0] = dp[i-1][0]转移一下。

参考博客:参考博客

 

参考题解:

分析:先设dp[i][j]表示小明在i分钟,疲劳值为j时所能走的最远距离。

a)、先看dp[i][0]的情况,表示第i分钟时,疲劳值为0,考虑这个值由哪些情况得到,1、dp[i][0] = dp[i-1][0],这个没有任何问题。2、dp[i][0] = dp[i-j][j]。表示i-j分钟时的疲劳值为j,然后一直休息j分钟把疲劳值降成0。

b)、现在考虑dp[i][j]的情况,它可以由dp[i-1][j-1] + Di得到,表示第i分钟选择走Di。因为要保证没有后效性,所以只有这一种情况可以转移。

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz