POJ 1700&NLG 47川を渡る問題（貪欲𞓜DP）

リンク:http://poj.org/problem?id=1700
http://acm.nyist.net/JudgeOnline/problem.php?pid=47
Description
A group of N people wishes to go acros a river with only one boat，which can at most carry two persons.The refore some sort of shute arrangement must be arranged in order to row the boat back and forth sont the panel operemant。the speed of a couple is determined by the speed of the slower one.Your job is to determine a strate that minimizes the time for the people to get acros.
Input
The first line of the input contains a single integer T(1==T==20)、the number of test cases.The n T cases follow.The first line of each case contains N、and the second line contains N integers giving the time for each people to cross the river.Each case is preceded by a blank line.The won't be more than 1000 people and nobody Tares more 100 second to cross.
Output
For each test case、print a line containing the total number of seconds required for all the N people to cross the river.
Sample Input

1
4
1 2 5 10

Sample Output

17

考え方の分析:
n=1,2,3の時に必要な最小時間が求められやすいです。今はn>=4で、n個人が単独で川を渡るために必要な時間が配列tに格納されていると仮定して、配列tを昇順に並べます。つまり配列に表示される時間は増加します。この時、単独で川を渡るために必要な時間が最も多い2人の旅行者を対岸に送ります。
    1>一番早いのは（時間t[0]と速いのは川を渡って、そして一番速いのは帰ってきて、また遅いのは川を渡って、それから速いのは帰ります。
    2>一番早いのと一番遅いのは川を渡って、そして一番早いのは帰ってきて、一番速いのと遅いのは川を渡って、そして一番速いのは帰ってきます。
    これで川を渡るのに一番時間がかかる二人を川に送りましたが、残りの人に対しては同じ処理をします。次にどのように使うべきかを判断する時間が一番少ないです。    1>シナリオ1に必要な時間は、t[0]+2**t[1]+t[n-1];
    2>シナリオ2に必要な時間は、2＊t[0]+t[n-2]+t[n-1];
    方式1が方式2より優れているなら、t[0]+2**t[1]+t[n-1]<2**t[0]+t[n-2]+t[n-1]化ジェーン：2**t[1]（注意：この問題の欲張り策はダイナミック！！！）
コードは以下の通りです

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXN 1000         //    
#define RST(N)memset(N, 0, sizeof(N))
using namespace std;

int s[MAXN];

int cmp(const void *a, const void*b) //         
{
    return *(int *)a - *(int *)b;
}

int main()
{
    int cas, n, k, st, a, b;
    scanf("%d", &cas);
    while(cas--) {
        scanf("%d", &n);
        for(int i=0; i<n; ++i) {
            scanf("%d", &s[i]);
        }
        qsort(s, n, sizeof(int), cmp);
        if(n == 1 || n == 2) {
            printf("%d
", s[n-1]);
            continue;
        }
        st = 0;
        if(n % 2) {            //           ，           
            st+= s[0] + s[1] + s[2];
        }else {
            st+= s[1];
        }
        k = (n - 2) / 2;                       //     
        for(int i=0; i<k; ++i) {                  //     
            a= s[0] + 2 * s[1] + s[n-1];
            b= 2 * s[0] + s[n-1] + s[n-2];
            if(a < b) {
                st += a;
            }else {
                st += b;
            }
            n -= 2;
        }
        printf("%d
", st);
    }
    return 0;
}