C++(clang++ 11.0.1) 解法, 执行用时: 28ms, 内存消耗: 1132K, 提交时间: 2022-09-04 15:38:59

#include<iostream>
using namespace std;
const int N=100000+5;
int t[N];
int d[N];
int main(){
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>t[i];
  }
  d[0]=t[0];
  d[1]=t[1];
  for(int i=2;i<n;i++){
    d[i]=min(d[i-1]+t[0]+t[i],d[i-2]+t[0]+t[i]+2*t[1]);
  }
  cout<<d[n-1];
}

Python3(3.5.2) 解法, 执行用时: 98ms, 内存消耗: 12140K, 提交时间: 2020-06-12 11:13:03

from sys import stdin as inn
n=int(input())
a,s=[],0
a.extend(sorted(map(int,inn.read().split("\n")[:-1])))
while len(a)>3:
    s+=min(a[0]+a[1]*2+a[-1],a[0]*2+a[-2]+a[-1])
    a.pop()
    a.pop()
if len(a)==3: print(s+sum(a))
else: print(s+a[-1])

pypy3 解法, 执行用时: 295ms, 内存消耗: 30008K, 提交时间: 2023-05-26 21:08:00

n = int(input())
arr = [int(input()) for _ in range(n)]

arr.sort()
dp = [999999999]*n
dp[0] = arr[0]
dp[1] = arr[1]
for i in range(2,n):
    dp[i] = min(arr[0]+arr[i]+dp[i-1], dp[i-2]+arr[i]+arr[0]+2*arr[1])
    
print(dp[-1])