一位牧民和一群数量为n的羊群，前方遇到一条小河，河边刚好有一条小船，假设小船足够大，可以一次载完所有羊，但是牧民会很累，船会划得很慢，但可以分批运过去：
如果载一只羊过河，需要M(1)分钟 ；
如果载两只羊过河，需要M(2)分钟 ；
如果载三只羊过河，需要M(3)分钟 ；
…………
牧民空船返回对岸需要M分钟 ；
求得最短时间将所有的羊运到河对岸。
很像一道智力题，但在计算机看来，两步就可以得到答案。
下面给出我的思维过程：
dp[n] 表示 把n只羊运送到河对岸需要的最少时间 ；
如果只有一只羊需要过河 ，需要的时间 ，用 M + M(1) 来表示 ; 把 M + M(1) 的值赋给 dp[1] ;
如果有两只羊需要过河，先算出把两只羊一块载过去需要多长时间 ，用M + M(1) + M(2)来表示 ；
然后再算，先载一只过去，再把另外一只载过去需要多长时间，用dp[1] + dp[1] + m 来表示 ;
比较一下两种方法，哪种时间用的最少，把最少的赋值给dp[2] ；
如果有三只羊需要过河，先算出把三只羊一块载过去需要多长时间，用M + M(1) + M(2) + M(3) 来表示 ；
然后再算，先载一只过去，再把另外两只载过去需要多长时间，用dp[1] + m + dp[2] 来表示 ；
然后再算，先载两只过去，再把另外一只载过去需要多长时间，用dp[2] + m + dp[1] 来表示 ；
比较一下三种方法，哪种时间用的最少，把最少的赋值给dp[3] ;
………… ；
这样分析之后，很容易联想到用动态规划解题。（求全局最优解）
下面给出相关代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23 |
#include<iostream>using
namespace std ;int main() { int
n ; cin >> n ; while(n--) { int
N , m ; cin >> N >> m ; int
dp[1100] , i ; dp[0] = m ; for(i = 1 ; i <= N ; i++) { int
t ; cin >> t ; dp[i] = dp[i-1] + t ; } for(i = 2 ; i <= N ; i++) for(int
j = 1 ; j < i ; j++) if(dp[i] > ( dp[j] + dp[i - j] + m)) dp[i] = dp[j] + dp[i-j] + m ; cout << dp[N] << endl ; } return
0 ;} |
原文：http://www.cnblogs.com/scottding/p/3611342.html