本文主要是介绍[Usaco2008 Mar]River Crossing渡河问题 简单DP,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Farmer John以及他的N(1 <= N <= 2,500)头奶牛打算过一条河,但他们所 有的渡河工具,仅仅是一个木筏。 由于奶牛不会划船,在整个渡河过程中,FJ必须始终在木筏上。在这个基础 上,木筏上的奶牛数目每增加1,FJ把木筏划到对岸就得花更多的时间。 当FJ一个人坐在木筏上,他把木筏划到对岸需要M(1 <= M <= 1000)分钟。 当木筏搭载的奶牛数目从i-1增加到i时,FJ得多花M_i(1 <= M_i <= 1000)分钟 才能把木筏划过河(也就是说,船上有1头奶牛时,FJ得花M+M_1分钟渡河;船上 有2头奶牛时,时间就变成M+M_1+M_2分钟。后面的依此类推)。那么,FJ最少要 花多少时间,才能把所有奶牛带到对岸呢?当然,这个时间得包括FJ一个人把 木筏从对岸划回来接下一批的奶牛的时间。
刚开始我以为每个奶牛有个运送时间。最后发现题目的意思只跟每次运送奶牛的个数有关系
然后就是一个简单的线性DP
dp[i] 表示运i个奶牛的最小花费
dp[i] = min(dp[i], dp[i - j] + sum[1...j] + M) j <= i
这篇关于[Usaco2008 Mar]River Crossing渡河问题 简单DP的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!