代码:
分两种情况:
1. 最快带最慢的两个过去
2. 最快带次快过去,次快回,最慢带次慢过去,最快回
贪心+dp/记忆化搜索
//
// Created by 徐志远 on 2019-09-26.
//
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N;
const int MAXN = 100000;
int a[MAXN];
int dp[MAXN];
int dfs(int x){
if(dp[x]) return dp[x];
if(x==1) return a[1];
if(x==2) return max(a[1],a[2]);
if(x==3) return a[3]+a[1]+a[2];
return dp[x]=dfs(x-2) + min(2*a[1]+a[x]+a[x-1],2*a[2]+a[x]+a[1]);
}
int main(){
memset(a,0,sizeof(a));
memset(dp,0,sizeof(dp));
cin>>N;
for(int i=1;i<=N;i++){
cin>>a[i];
}
sort(a+1,a+N+1);
cout<<dfs(N)<<endl;
return 0;
}```