Bridge over a rough river
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 4143   Accepted: 1703

Description

A group of N travelers (1 ≤ N ≤ 50) has approached an old and shabby bridge and wishes to cross the river as soon as possible. However, there can be no more than two persons on the bridge at a time. Besides it's necessary to light the way with a torch for safe crossing but the group has only one torch.

Each traveler needs ti seconds to cross the river on the bridge; i=1, ... , N (ti are integers from 1 to 100). If two travelers are crossing together their crossing time is the time of the slowest traveler.

The task is to determine minimal crossing time for the whole group.

Input

The input consists of two lines: the first line contains the value of N and the second one contains the values of ti (separated by one or several spaces).

Output

The output contains one line with the result.

Sample Input

4
6 7 6 5

Sample Output

29

Source

Northeastern Europe 2001, Western Subregion
 
想不到的说....
题意:n个人过河,每次能过去两个人,这两个人带了手电筒,过了河之后需要有个人送回来,问所有人通过的最少时间.
 
题解:要是想成每个人过河的时候要时间最短的人送回来,然后耗时最短和耗时最长的一起回去那就错了,比如说:
四个人过桥花费的时间分别为 1 2 5 10,按照上面的想法答案是19,但是实际答案应该是17。
      

具体步骤是这样的:
      

第一步:1和2过去,花费时间2,然后1回来(花费时间1);
      

第二歩:3和4过去,花费时间10,然后2回来(花费时间2);
      第三部:1和2过去,花费时间2,总耗时17
 
贪心想法:对于第i个人,1.如果已经有i-1个人已经过了河,那么肯定是派时间最短的过来接他:dp[i] = dp[i-1]+a[1]+a[i];
2.如果已经有i-2个人已经过了河,那么第一步,先派耗时最短的来接他,然后给手电筒给a[i]和a[i-1],然后再派耗时次小的
人过来,耗时a[2],然后一起回去耗时a[2] dp[i] = dp[i-2]+a[i]+a[1]+2*a[2];
dp[i] = max(1,2)
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; int a[],dp[];
int main(){
int n;
while(scanf("%d",&n)!=EOF){
for(int i=;i<=n;i++) scanf("%d",&a[i]);
memset(dp,,sizeof(dp));
sort(a+,a+n+);
dp[] = a[];
dp[] = a[];
for(int i=;i<=n;i++){
dp[i] = min(dp[i-]+a[i]+a[],dp[i-]+a[i]+*a[]+a[]);
}
printf("%d\n",dp[n]);
}
}

poj 1700(java大数据版):注意处理n=1的特殊情况

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner; public class Main {
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
int tcase= sc.nextInt();
while(tcase-->){
int n =sc.nextInt();
if(n==) {
int v = sc.nextInt();
System.out.println(v);
continue;
}
BigInteger [] a = new BigInteger[n+];
BigInteger [] dp = new BigInteger[n+];
for(int i=;i<=n;i++){
int v = sc.nextInt();
a[i] = BigInteger.valueOf(v);
}
Arrays.sort(a,,n+);
//for(int i=1;i<=n;i++) System.out.println(a[i]);
dp[] = a[];
dp[] = a[];
for(int i=;i<=n;i++){
BigInteger c1 = dp[i-].add(a[i]).add(a[]);
BigInteger c2 = dp[i-].add(a[]).add(a[].multiply(BigInteger.valueOf())).add(a[i]);
if(c1.compareTo(c2)>) dp[i] = c2;
else dp[i] = c1;
}
System.out.println(dp[n]);
}
} }

最新文章

  1. CozyRSS开发记录-中断
  2. JavaScript 数组详解
  3. django 的模板语言
  4. JSP标准标签库(JSTL)之核心标签(上)
  5. OTG 接口烧写最小Linux的方法
  6. Solr集群搭建
  7. 【学习】ie8支持rgba()透明度颜色
  8. 6.C++初步分析类
  9. maven项目与普通项目的区别
  10. Spark MLlib
  11. Sumdiv POJ - 1845 (逆元/分治)
  12. CentOS 7 keepalived+LVS
  13. arcengine右键实现new group layer的功能
  14. Linux常用网络工具:Http压力测试之ab
  15. StreamSets学习系列之StreamSets的Core Tarball方式安装(图文详解)
  16. Shell中各种判断语法
  17. SSL延迟有多大 (Https)
  18. 测试一下你的T-SQL基础知识-count
  19. PHP webservice 的初接触
  20. 【python】win10中python3.5.2输入pip出现Fatal error in launcher: Unable to create process using &#39;&quot;&#39;

热门文章

  1. 自动清理N天前的二进制日志
  2. Codeforces Round #344 (Div. 2) A
  3. MYSQL性能察看
  4. opencv学习笔记二
  5. Nginx的启动、停止、平滑重启
  6. asyncio 实现 aiohttp
  7. Druid连接池及监控在spring中的配置
  8. VS开发工具 因插件问题导致 已停止工作 解决办法
  9. hdu 1166敌兵布阵(线段树)
  10. Android控件——AutoCompleteTextView与MultiAutoCompleteTextView(实现自动匹配输入的内容)