Skip to content

14060: 【原4060】最优潜水策略设计

题目

题目描述

author: 程序设计思想与方法助教李天格 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4060 ## 问题描述 某单位在某个湖里举行潜水比赛,这是一个团体项目,每一支队伍由n个人组成,要求所有队员从起点(A岸)潜水到终点(B岸)。在潜水时必须使用氧气瓶,但是每支队伍只有一个氧气瓶。最多两人同时使用一个氧气瓶,但此时两人必须同步游泳,因此两人到达终点的时间等于较慢的一个人单独游到终点所需的时间。大家都很友好,任何两个人都愿意一起游泳。安排一种潜水策略,使得最后一名队员尽早到达终点。编写一个程序,首先输入某个队伍人数n(n<100),接着依次输入n个队员游到终点的时间(非递减序),输出所有队员最早到达终点的时间。

输入输出描述

输入

-输入一个正整数n,以及一行n个非递减正整数。

输出

所有队员最早到达终点的时间

程序运行实例

Sample Input

3 1 3 4

Sample Output

8

zqy2018's solution

#include <bits/stdc++.h>
using namespace std;
int a[105], n, g[105];
int main(){
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    memset(g, 0x3f, sizeof(g));
    g[n] = 0;
    for(int i = n; i >= 3; --i){
        g[i - 2] = min(g[i - 2], g[i] + 2 * a[2] + a[1] + a[i]);
        g[i - 1] = min(g[i - 1], g[i] + a[1] + a[i]);
    }
    g[0] = min(g[2] + a[2], g[1] + a[1]);
    cout << g[0] << endl;
    return 0;
}