第六届河南省程序设计大赛——H River Crossing（简单动态规划）

曾经终败给现在 2022-04-24 23:12 168阅读 0赞

## 题目描述: ##

Afandi is herding N sheep across the expanses of grassland when he finds himself blocked by a river. A single raft is available for transportation.

Afandi knows that he must ride on the raft for all crossings, but adding sheep to the raft makes it traverse the river more slowly.

When Afandi is on the raft alone, it can cross the river in M minutes When the i sheep are added, it takes Mi minutes longer to cross the river than with i-1 sheep (i.e., total M+M1 minutes with one sheep, M+M1+M2 with two, etc.).

Determine the minimum time it takes for Afandi to get all of the sheep across the river (including time returning to get more sheep).

## 输入描述: ##

<span style="color:#000000">On the first line of the input is a single positive integer k, telling the number of test cases to follow. 1 ≤ k ≤ 5  Each case contains:
    
    * Line 1: one space-separated integers: N and M      (1 ≤ N ≤ 1000 , 1≤ M ≤ 500).
    
    * Lines 2..N+1:  Line i+1 contains a single integer: Mi  (1 ≤ Mi ≤ 1000)
    </span>

## 输出描述: ##

<span style="color:#000000">For each test case, output a line with the minimum time it takes for Afandi to get all of the sheep across the river.</span>

## 样例输入: ##

复制

2    
    2 10   
    3
    5
    5 10  
    3
    4
    6
    100
    1

## 样例输出: ##

18
    50

题很简单，怪我英语太不好，好久没看懂咋回事，最后还是看样例看懂了

输入包含n和m

以及n个耗时

n代表有n只羊，m代表空船耗时

意思就是如果空船过和耗时就是m

如果带f只羊过河就是m+m1+m2，，，，，+mf

使用动态规划就行

ac代码：

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    using namespace std;
    int main(){
    	int t,dp[1005],a[1005];
    	cin>>t;
    	while(t--){
    		int n,m;
    		cin>>n>>m;
    		dp[0]=m;   //空船耗时m 
    		for(int i=1;i<=n;i++){
    			cin>>a[i];
    			dp[i]=dp[i-1]+a[i];   //带上i只羊初始耗时 
    		}
    		for(int i=1;i<=n;i++){
    			for(int j=1;j<i;j++){
    				dp[i]=min(dp[i],dp[i-j]+dp[j]+m);  //将i只羊分为两批运，一批i-j只，一批j只 因为分两批所以中间要空船返回一下 
    			}
    		}
    		cout<<dp[n]<<endl;
    	}
    	return 0;
    }