题解

liuxy1234 · 2022-04-23 11:35:30 · 题解

这道题其实就是小学奥数，有 2 种方法：

1. 快者来回

   就是最快的人送最慢的过去再回来。

2. 慢者同行

   就是第 1 和 2 快的人过去，最快的人回来，再让最慢的两个人过去，第二快的再回来。

分析完之后，我们就可以写代码了。

#include<iostream>
#define int long long
using namespace std;

const int maxn=100005;
int n,a[maxn];
int dp[maxn];

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    dp[n]=a[n]+a[1];
    for(int i=n-1;i>=1;i--)
    {
       dp[i]=min(a[i]+a[1]+dp[i+1],a[i+1]+2*a[2]+a[1]+dp[i+2]);
    }
    cout<<dp[3]+a[2];
    return 0;
}