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