作业帮ACM 关于动态规划的疑问某旅游城市在长江边开辟了若干个旅游景点.一个游船俱乐部在这些景点都设置了游船出租站,游客可在泽泻游船出租站租用游船,并在下游的任何一个游船出租站归还游
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/07 20:44:07
ACM 关于动态规划的疑问某旅游城市在长江边开辟了若干个旅游景点.一个游船俱乐部在这些景点都设置了游船出租站,游客可在泽泻游船出租站租用游船,并在下游的任何一个游船出租站归还游
ACM 关于动态规划的疑问
某旅游城市在长江边开辟了若干个旅游景点.一个游船俱乐部在这些景点都设置了游船出租站,游客可在泽泻游船出租站租用游船,并在下游的任何一个游船出租站归还游船,从一个悠长出租站到下游的游船出租站间的租金明码标价.你的任务是为游客计算从起点站到终点之间的最少租船费用.
输入样例
3
2 3 6 //从起点到第1 ,2 ,3个站的租金,下同
1 3
2
3
4 7 9
4 5
6
输出样例
case 1:5
case 2:9
一个DP的思路是（当然不是最好的DP方法）
m[i][j]=min {m[i][k]+m[k][j] ,r[i][j] }
这是书上的方法当然是对的
我的问题是第二个m[k][j]改成r[k][j],也就是认为k到j是直达的
m[i][j]=min {m[i][k]+r[k][j] ,r[i][j] }
如何判断算法正确性?
ACM 关于动态规划的疑问某旅游城市在长江边开辟了若干个旅游景点.一个游船俱乐部在这些景点都设置了游船出租站,游客可在泽泻游船出租站租用游船,并在下游的任何一个游船出租站归还游
第二种做法完全正确.假设在“从i到j花费最少价钱的路线”中,j前的一站是k,那么这种做法就必然可以取到正确答案.因为在i到j的最优路线中,从i到k的路线选取也必然是最优的.
另外必须理解的是,采取第二种做法后,当i!=0时,m[i][j]既不用求得,也不需要用它推导其它量,m[i][j]只有当i=0时才有用,所以m数组直接简化为一维就可以了,所以第二种方程的实质就是最好的方法.时间复杂度O(N^2),不可能继续优化.
是一道最简单的DP,没什么难的.算法正确性可以严格证明,但在ACM里一般找找反例多想一想就行了