1232：Crossing River

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

【输入】
输入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;
}