题目：过河

思路：动态规划

1. 考虑答案会包含哪些数。当前数组中的最大值必然会包含在答案内，因为每次过河的时间会取两数中的最大值。
2. 最大的数在何时过河不影响答案，但是可以通过选择与其一同过河的数最小化答案。将数组从小到大排序，最大值和次大值一同过河是一种方案（可以思考，如果最大值和非次大值一同过河，最大值所做的贡献明显没那么大）。每次过河后如果要回来，必然是已经过河的数中最小值。因此最大值也可以和最小值作为最后一对一起过河，这是另外一种方案。

代码如下：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;

public class Main {
	//快速输入
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	//快速输出
	static PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
	
	public static void main(String[] args) throws IOException {
		String[] s=br.readLine().split(" ");
		int n=Integer.parseInt(s[0]);
		s=br.readLine().split(" ");
		long[] nums=new long[n];
		for(int i=0;i<n;i++) {
			nums[i]=Long.parseLong(s[i]);
		}
		//将数组排序
		Arrays.sort(nums);
		//对于n=1,2,3可以直接返回答案
		if(n==1) {
			pw.println(nums[0]);
		}
		else if(n==2) {
			pw.println(nums[1]);
		}
		else if(n==3) {
			pw.println(nums[0]+nums[1]+nums[2]);
		}
		else {
			//dp[i]代表前i个数过河所需要的最小时间
			long[] dp=new long[n+1];
			dp[1]=nums[0];
			dp[2]=nums[1];
			dp[3]=nums[0]+nums[1]+nums[2];
			for(int i=4;i<=n;i++) {
				//前者为最大值和次大值一同过河，因为前i-2个人过河之后需要将船划回来，这时候选择过河后的数中的最小值。最大值和次大值过河后，河对面还有一个最小值没有过来，于是让当前岸最小值过去与其一同过来
				//后者为最大值与最小值一同过河
				//取两者的最小值
				dp[i]=Math.min(nums[i-1]+dp[i-2]+nums[0]+nums[1]*2, dp[i-1]+nums[0]+nums[i-1]);
			}
			pw.println(dp[n]);
		}
		pw.flush();
	}
}