当前位置: 首页 > 工具软件 > River Trail > 使用案例 >

1232:Crossing River

艾修然
2023-12-01

【题目描述】
几个人过河,每次过两人一人回,速度由慢者决定,问过河所需最短时间。

【输入】
输入t组数据,每组数据第1行输入n,第2行输入n个数,表示每个人过河的时间。

【输出】
输出t行数据,每行1个数,表示每组过河最少时间。

【输入样例】
1
4
1 2 5 10

【输出样例】
17
思路:动态规划,设dp[n]表示n个人过完河所需的时间。

可以先将数组排序,过河时间最短的人在前面,即a[1]. 过河有两种情况分析

1.倒着思考:当n个人过完河,手电筒也跟着过来了。所以当n-1人过完河时,手电筒也是跟着过来了。(花费时间最短时间dp[n-1])

当桥边只剩一个人时,可以让花费时间最少的那个人a[1]过来送手电筒,人员n和人员1一同过河,花费时间为a[n]; 则dp[n]=dp[n-1]+a[n]+a[1];

2.当桥边剩两个人时,即n-2人已经过河(时间为dp[n-2]),这样人员1先去送手电(时间a[1]),然后人员n和人员n-1同时过河,(时间为a[n]),然后人员2来送手电(时间为a[2]),然后人员1和人员2过桥(时间为a[2]) dp[n]=dp[n-2]+a[1]+2*a[2]+a[n];

最短时间:dp[n]=min( dp[n-1]+a[n]+a[1] , dp[n-2]+a[1]+2*a[2]+a[n] );

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
int a[N],dp[N];
int main(){
 int T;
 int n;
 cin>>T;
 while(T--){
 	cin>>n;
 	for(int i=0;i<n;i++)
	 cin>>a[i];
	 sort(a,a+n);
	 dp[0]=a[0];
	 dp[1] =a[1];
	 for(int i=2;i<n;i++)
	 dp[i] = min(dp[i-1]+a[0]+a[i],dp[i-2]+a[0]+a[i] + a[1]*2);
 
	cout<<dp[n-1]<<endl;
}	
	return 0;
} 
 类似资料:

相关阅读

相关文章

相关问答