poj-1700 Crossing River

本文主要是介绍poj-1700 Crossing River，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://poj.org/problem?id=1700

此题讲的是N个人过河，每个人都有自己的过河时间，一条船只能承受2个人，所用时间为其中过河时间最多的，所以呢，想到有两种情况，第一种：过河时间最少的人来回接送其他人，第二种：过河时间最少和次少的人来回接送其他人，刚开始就觉得第一种时间必然是最少的，但是仔细想想，不然。因为第一种情况虽然单次过河时间少，但送人的次数要多，如第1个人（过河时间最少）接送第i人 dp[i]=dp[i-1]+time[0]+time[i]； 而第二种情况呢，虽然来回次数多，但是接送的人要多，如第1个人接送第2个人过河，第二个人回来，再让第i和i-1个人过去，然让第1个人回来...

样例是1 2 5 10   所以可以让1、2过去 2回来  花费3   再让5、10过去 1 回来  所以总花费是17

#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#define N 1005
using namespace std;
int cmp(const void *a,const void *b)
{return *(int *)a-*(int *)b;
}
int a[N];
int dp[N];
int n;
int main()
{int i,j,t,k;int min1,min2;scanf("%d",&t);while(t--){scanf("%d",&n);for(i=0; i<n; i++)scanf("%d",&a[i]);qsort(a,n,sizeof(a[0]),cmp);dp[0]=a[0];//a[0]一个人dp[1]=a[1];//a[1],a[0]两个人中的最大一个for(i=2; i<n; i++){min1=dp[i-1]+a[i]+a[0];min2=dp[i-2]+a[1]+a[0]+a[i]+a[1];//最快的和次快的过去，次快的回来，所以a[1]+a[1];//最慢的和次慢的过去，最快的回来，所以a[i]+a[0];dp[i]=min(min1,min2);  //取小的}printf("%d\n",dp[n-1]);}return 0;
}

这篇关于poj-1700 Crossing River的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---