C++动态规划题目求解
发布网友
发布时间：2022-04-29 22:24
共1个回答
热心网友
时间：2022-06-24 12:11
这里有一个O(n*m)的算法
用f[i][j][0/1]表示第i分钟后体力还剩j的最大距离
最后一维0表示这分钟休息，1表示前进
初始化：f[0][m]=0,其余f[i][j]=-inf
转移方程：
第i分钟选择走则
f[i][j][1]=max(f[i-1][j+1][1]+d[i])
特判刚休息好
f[i][m-1][1]=max(f[i-1][m][0]+d[i])
选择休息则
f[i+m-j-1][m][0]=max(f[i-1][j][1])
有时需要满血休息，要特判
f[i][m][0]=max(f[i-1][m][0])
这里是直接将上一回合前进完剩余j体力的数据转移到休息完的回合处。
最后f[n][m][0]就是答案（因为要满体力走，所以最后一轮一定休息）
下面是伪代码：
初始化略
for i=1 to n
for j=0 to m-2
f[i][j][1]=max(f[i-1][j+1][1]+d[i])
f[i][m-1][1]=max(f[i-1][m][0]+d[i])
for j=0 to m-1
f[i+m-j-1][m][0]=max(f[i-1][j][1])
//特判满血休息的情况
f[i][m][0]=max(f[i-1][m][0])
//注意max是和原来的值比较
结束输出f[n][m][0]
。。
纯手打，望采纳，谢谢。
