2534 渡河

2013年市队选拔赛广州

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 黄金 Gold

题目描述 Description

有N个人需要渡河到对岸，但是只有一条小船，只能乘坐两人，请问怎么能够让他们以最少的时间渡河到对岸呢？

输入描述 Input Description

输入为两行，第一行为渡河的人数N (1<=N<=1000)

第二行为N个正整数，范围是 [1,100]，代表他们划船到对岸需要多少分钟

输出描述 Output Description

输出只有一行，代表最短的渡河时间，单位为分钟

样例输入 Sample Input

2 3 50

样例输出 Sample Output

数据范围及提示 Data Size & Hint

N (1<=N<=1000)

思路：

动态规划，先排序，只有1个人和两个人是就是较慢的人的时间，多于两人时，有两种情况，在两种情况中却最小值，

第一种情况是由1号划回船，再把 i 个接过去，就是 f[i-1]+a[1]+a[i]
第二种情况是1号2号先过去，2号回，然后 i-1 和 i 号过去，1号回，最后1和2号过去，就是 f[i-2]+a[1]+a[i]+a[2]+a[2]

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int n;
 7 long long a[100001];
 8 long long f[100001];
 9 long long ans;
10 
11 int main()
12 {
13     scanf("%d",&n);
14     for(int i=1; i<=n; i++)
15         scanf("%d",&a[i]);
16     sort(a+1,a+n+1);
17     f[1]=a[1];
18     f[2]=a[2];
19     for(int i=3; i<=n; i++)
20         f[i]=min(f[i-1]+a[1]+a[i],f[i-2]+a[2]+a[1]+a[i]+a[2]);
21     cout<<f[n];
22 }