题目描述

有n个人希望在晚上通过一座桥。在任何时刻，最多只能有两个人在桥上，并且必须要带着手电筒才能通过桥。现在的麻烦是只有一个手电筒，所以必须安排某种顺序，使得手电筒可以被带回去让更多的人过桥（手电筒必须由人带回，不可以从对岸扔过去）。 每个人都有不同的过桥时间，两个人一起过桥所用的时间等于其中较慢的一个。你的任务是要找出能在最短时间内使所有人都过桥的方案。

输入

第一行是一个整数n。 接下来有n行，每一行给出一个人的过桥时间（整数，单位：秒）。 每个人的过桥时间不超过100秒。

输出

输出一行一个数，表示所有人过桥的最短时间。

思路

排序后递推，f[i]=min(f[i−1]+a[1]+a[i],f[i−2]+a[1]+a[2]∗2+a[i])

#include 
#include 
using namespace std;
long long a[1002],f[1002];
int i,j,k,n,m,s,x,y;
long long ans;
__attribute__((optimize("O2")))
int min(int x,int y)
{
    if (x>y) return y;
    else return x;
}
__attribute__((optimize("O2")))
int main()
{
    scanf("%d",&n);
    for (i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    f[1]=a[1];
    f[2]=a[2];
    for (i=3;i<=n;i++)
    {
         f[i]=min(f[i-1]+a[1]+a[i],f[i-2]+a[1]+a[2]*2+a[i]);
    }
    printf("%d\n",f[n]);
    return 0;
}