poj 1700 过河问题

参考blog: http://www.cnblogs.com/steady/archive/2011/01/23/1942555.html

http://blog.csdn.net/wuzhekai1985/article/details/6846934

上面两篇blog都给出了该怎么做，而且非常详细，但是没给出为什么这么做。

我试着证明了一下，我感觉这个题的策略其实就是把行动最慢的两个人送过去花费的时间最短。那么这道题的最终结果将是最优的。

因为送两个人过河所花费的最小时间已经证明出来了。然后就以每两个两个的去送，那么就形成了递归。但是送以两个人两个人的去送，这时时间一定是最优的吗？以三个三个人去送为什么就不行呢?

不知道对不对希望有大神能指点一下。

#include<cstdio>
#include<algorithm>
using namespace std;
int sum = 0;
int Cross_river(int *input,int num)
{
 
 
    if(num <= 2) return input[num-1];
    else if(num == 3)return input[0]+input[1]+input[2];
    else{
        int t1=input[0]+input[1]*2+input[num-1];
        int t2=input[0]*2+input[num-1]+input[num-2];
        int tmp=0;
        tmp = t1>t2?t2:t1;
        return Cross_river(input,num-2)+tmp;
    }
}
 
 
int main()
{
    int T_c,num,input[1005];
    scanf("%d",&T_c);
    while(T_c--)
    {
        scanf("%d",&num);
        for(int i = 0;i < num;++i)
        {
            scanf("%d",&input[i]);
        }
        sort(input,input+num);
 
        sum = Cross_river(input,num);
        printf("%d\n",sum);
    }
 
    return 0;
}