luogu p1809

代码：

分两种情况：

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;
}```