题目： 在一个夜黑风高的晚上，有n（n <= 50）个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，所以每次过桥的两个人需要把手电筒带回来，i号小朋友过桥的时间为T[i]，两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。

输入：

两行数据：第一行为小朋友个数n

第二行有n个数，用空格隔开，分别是每个小朋友过桥的时间。

输出：

一行数据：所有小朋友过桥花费的最少时间。

样例：

输入

4

1 2 5 10

输出

17

首先1和2先过去，t=2
随后1拿着手电筒回来，t=2+1=3
然后5和10一块过去， t=3+10=13
随后2拿着手电筒回来， t=13+2=15
最后1和2再拿着手电筒过桥， t=15+2=17

讯享网

测试用例给的这个还有一个很大的隐藏用途。这个问题着手，我是在想如何用动态规划算法解，想找到最优子结构。我以为始终把手电筒给到最大和次大让他们过去就是最优，然而不是这样。

我们可以把测试用例变一下，变成1 4 5 10。结果刚才的想法就是错的。最优的情况是1分别将5和10送过去。从而是最优的，和刚才的5和10直接过去不符，也就是和我最初的想法‘始终把手电筒给到最大和次大让他们过去就是最优’是不符的。那怎么找？没有任何依赖关系啊。因为始终找不到任何一个最优子结构。

那么就要去想怎么产生的两种截然不同的情况。这是因为如果是1 4 5 10的话，我们分两种情况考虑。首先是，4过去，1回来准备分别将5和10送过去。那么就会有，5过去了，1回来，10过去了，结束；另一情况是4过去，1回来，将手电筒给5和10。那么就会有，10过去，4回来，4再过去，结束。（先说明一下是两个人过桥，这里只是说了两人过桥的最长的过桥时间）

我们将这么模型提取出来，就是：
5过去了，1回来，10过去了
10过去，4回来，4再过去
也就是说两个4替换了一个5一个1。如果是1 2 5 10呢，那就是两个2替换了一个5一个1。这就是产生两种情况的问题所在。我们可以继续从测试用例入手，考虑1 3 5 10,结果发现，两种情况居然是一样的时间。这个是从测试用例入手进行考虑的。

因此我们可以考虑两种情况：1、将最小花费时间把手电筒送回来，然后将下一个人送过去。2、将最小花费时间把手电筒送回来，然后给到其中两个人，然后次小花费时间把手电筒送回来，再和最小花费时间的一起过桥。
什么时候满足条件1呢？当然是绑定两人花费时间最少的那个人的时间+最小花费时间未超过2*次小花费时间。其他的情况都符合条件2。
这就会产生最优子结构，就是那个此时的最少花费时间。

因此我们就会有
首先将这几个花费时间按升序排序
t[i]：第i个人过桥的花费时间
p[i]: 第i个人过桥的最少花费时间
p[i]=p[i-1]+t[1]+t[i] ，2·t[2]>t[1]+t[i-1]
p[i]=p[i-2]+t[1]+t[i]+2*t[2] ,2·t[2]<=t[1]+t[i-1]

递归方程列出来了，但是不管怎么说顶上那两种情况，也像是一种贪心策略，因为看着还是有瑕疵的啊。

在条件2中，如果最小的把手电筒拿给另外两个人，让这两个人过去后，将次小的回来，++然后最小的要把次小的送回去++。这个操作就很迷，万一又来个人呢，还是要先将次小的送回去？没错，

你认为可能先将最小的把这个人送过去，然后自己再回来呀（D1）；又或者是直接把灯扔给他，将次次小的把灯送回来（D2）。还有，万一来两个人呢？也有可能把灯直接扔给两个人，让他们先过去，然后让次次小的再把灯送回来（D3），或者还是直接把灯给其中一个人送过去（D4）。

先证明第一个瑕疵：



再证明第二个瑕疵：
不过这个情况一二，就是有四个人的时候怎么过桥可以按照顶上的所述分成两种情况

从而说明了我的两个贪心策略是正确的
以这个思路来编写代码：

import java.util.Arrays; import java.util.Scanner; public class Main { 
    public static void main(String[] args) { 
    // TODO Auto-generated method stub Scanner scanner=new Scanner(System.in); int n=scanner.nextInt(); int a[]=new int[n]; for(int i=0;i<n;i++) a[i]=scanner.nextInt(); Arrays.sort(a); int p[]=CrossBridge(a); if(a.length>0) { 
    if(a.length==1) System.out.println(p[0]); else System.out.println(p[a.length-2]); } else System.out.println(0); } public static int[] CrossBridge(int a[]) { 
    int p[]=new int[a.length]; //记录过桥时间 if(a.length==0) //没有人过桥 return p; if(a.length>0) { 
    if(a.length==1) { 
    p[0]=a[0]; //只有一个小朋友 return p; } else if(a.length==2) { 
    p[0]=a[1]; //只有两个小朋友 return p; }else { 
    //含三个及三个以上的小朋友 p[0]=a[1]; p[1]=a[0]+a[1]+a[2]; } } for(int i=2;i<p.length-1;i++) { 
    if(2*a[1]<=a[i]+a[0]) //如果次小的超过了a[i]和a[0],则a[i+1]与a[i]一起过桥，让a[1]送手电筒回来 { 
    p[i]=p[i-2]+a[0]+a[i+1]+2*a[1]; //先让最小的送手电筒回来，然后a[i+1]与a[i]一起过桥 //再让次小的送灯回来，随后把最小的接过去。 } else { 
    //否则就是最小的和a[i+1]一起过桥 p[i]=p[i-1]+a[0]+a[i+1]; //先让最小的把手电筒送回来，再接着a[i]一起过桥 } } return p; } }

为了说明，这个思路是正确的。我特意找了POJ系统进行了测试

测试通过！