Crossing River(1700poj)
2024-08-30 05:36:28
Crossing River
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 9919 | Accepted: 3752 |
Description
A group of N people wishes to go across a river with only one boat, which can at most carry two persons. Therefore some sort of shuttle arrangement must be arranged in order to row the boat back and forth so that all people may cross. Each person has a different rowing speed; the speed of a couple is determined by the speed of the slower one. Your job is to determine a strategy that minimizes the time for these people to get across.
Input
The first line of the input contains a single integer T (1 <= T <= 20), the number of test cases. Then 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. There won't be more than 1000 people and nobody takes more than 100 seconds 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 ps:http://poj.org/problem?id=1700
/* 此题讲的是N个人过河,每个人都有自己的过河时间,一条船只能承受2个人,所用时间为其中过河时间最多的,
所以呢,想到有两种情况,第一种:过河时间最少的人来回接送其他人,第二种:过河时间最少和次少的人来回接送其他人,
刚开始就觉得第一种时间必然是最少的,但是仔细想想,不然。因为第一种情况虽然单次过河时间少,但送人的次数要多,
如第1个人(过河时间最少)接送第i人 dp[i]=dp[i-1]+time[0]+time[i]; 而第二种情况呢,虽然来回次数多,但是接送的人要多,
如第1个人接第i-1个和第i个人,然后让第i-1个和第i个人一块过河,第2个人再接送第1个人。
dp[i]=dp[i-2]+time[0]+time[i]+time[1]*2。所以每次计算出这两个值都应该进行比较,从而AC!*/
#include<stdio.h>
#include<stdlib.h>
#define N 1010 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=;i<n;i++)
scanf("%d",&a[i]);
qsort(a,n,sizeof(a[]),cmp);
dp[]=a[];
dp[]=a[]; for(i=;i<n;i++)
{
min1=dp[i-]+a[i]+a[];
min2=dp[i-]+a[]+a[]+a[i]+a[];
dp[i]=min1;
if(min1>min2)//中间是嵌套的,哪种快选哪种
dp[i]=min2;
}
printf("%d\n",dp[n-]);
}
return ;
} /*
3
6
1 2 5 10 15 20
5
1 2 5 10 15
4
1 2 5 10
*/
最新文章
- ABBYY FineReader 12对系统有哪些要求
- Java4Android
- xml基础学习笔记05
- [二]JFreeChart实践一
- 最快让你上手ReactiveCocoa之基础篇(简称RAC)
- 项目DEMO下载
- Python源码分析
- (二十六)svn的问题二
- 生成式模型之 GAN
- ruby写一个文件内容相似性比较的代码
- Django入门五之admin管理
- MySQL注入与防御
- Vue.js 系列教程 1:渲染,指令,事件
- 阿里云服务器使用镜像市场上的环境以后sql不能远程问题
- shell启动执行cypher语句
- js异常处理
- js弹出div层内容(按回退键关闭div层及遮罩)
- [转贴]systemd 编写服务管理脚本
- 51nod 1040 最大公约数之和 欧拉函数
- 【C++】全排列