POJ 1700 & NYLG 47 过河问题（贪心 || DP）

链接 ：http://poj.org/problem?id=1700

http://acm.nyist.net/JudgeOnline/problem.php?pid=47

Description

Input

Output

Sample Input

1
4
1 2 5 10

Sample Output

17

思路分析 :

当n=1,2,3时所需要的最小时间很容易求得,现在由n>=4,假设n个人单独过河所需要的时间存储在数组t中,将数组t按升序排序,即数组中所表示的时间是递增的.
那么这时将单独过河所需要时间最多的两个旅行者送到对岸去,有两种方式:

    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]<t[0]+t[n-2]
    即此时只需比较2*t[1]与t[0]+t[n-2]的大小关系即可确定最小时间,此时已经将单独过河所需时间最多的两个人送过了河,那么剩下过河的人数为:n-=2,采取同样的处理方式.

（注意：此题的贪心策略是动态的！！！）

代码如下：

#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\n", 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\n", st);
    }
    return 0;
}

POJ 1700 & NYLG 47 过河问题（贪心 || DP）,布布扣,bubuko.com

POJ 1700 & NYLG 47 过河问题（贪心 || DP）

原文：http://blog.csdn.net/keshacookie/article/details/23116935