AtCoder

分析

可以发现题目中的贡献只有加，按照鸡贼的话来说这是一个很罕见的性质。

倒着看整个过程，相当于每次往里面加一个数。

我们考虑每个数对答案的贡献。假设当前有若干个数，第 $i$ 个数的贡献是 $x_i$，那么我们在 $i,i+1$ 中加一个数，新加的数的贡献显然是 $x_i+x_{i+1}$。

这个 $i,i+1$ 对应原序列中的一段区间，因此可以 DP。设 $dp_{l,r,xl,xr}$ 表示 $[l,r]$ 区间，$l$ 对答案的贡献是 $xl$，$r$ 对答案的贡献是 $xr$，枚举最后加入的点可以得到转移
$$
dp_{l,r,xl,xr}=\min_{l<i<r}\left\{dp_{l,i,xl,xl+xr}+dp_{i,r,l+xr,xr}+(xl+xr)a_i\right\}
$$
答案是 $a_1+a_n+dp_{1,n,1,1}$。

可以证明复杂度是 $\mathcal{O}(2^n\operatorname{poly}(n))$ 的，反正能过。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=18+10;

int n,a[N];

ll dfs(int l,int r,int xl,int xr) {
    if (r-l+1<=2) return 0;
    ll res=1e18;
    for (int i=l+1;i<=r-1;++i)
        res=min(res,dfs(l,i,xl,xl+xr)+dfs(i,r,xl+xr,xr)+1ll*a[i]*(xl+xr));
    return res;
}

int main() {
    n=read();
    for (int i=1;i<=n;++i) a[i]=read();
    printf("%lld\n",dfs(1,n,1,1)+a[1]+a[n]);
    return 0;
}