Skip to content

Latest commit

 

History

History
13 lines (8 loc) · 1.14 KB

File metadata and controls

13 lines (8 loc) · 1.14 KB

dp[i][j][0/1]表示第i分钟结束时疲劳度为j, 且这一分钟是在休息(0), 或者运动(1)的情况下牛跑的最大距离

对于dp[i][j][0], 由于这一分钟是在休息, 则上一分钟结束时疲劳度为j+1(j为0则上一分钟的疲劳度也有可能为0),
所以把dp[i - 1][j + 1][0]和dp[i - 1][j + 1][1]中大的赋值给dp[i][j][0],
然后若j为0, 则dp[i - 1][0][0]也要被统计, 因为疲劳度为0时休息不会降低疲劳度

对于dp[i][j][1], 由于这一分钟是在运动, 所以上一分钟结束时疲劳度为j-1,
所以dp[i][j][1] = dp[i - 1][j - 1][1] + d, d是这一分钟可以走的距离.
如果上一分钟要休息, 则上一分钟结束时疲劳度要为0, 因为牛只能休息道0才可以开始运动, 故在j-1为0时, dp[i][j][1] = dp[i - 1][0][0] + d, 这时dp[i - 1][0][1]不需要被统计, 因为任何一分钟只要是在运动, 该分钟结束时疲劳度不可能为0, 而j-1为0, 就是说上一分钟结束时疲劳度为0那么上一分钟不可能在运动

最后输出dp[n][0][0], 最后一分钟结束, 疲劳度为0, 且由于疲劳度为0, 所以最后一分钟只能休息