测评链接

题目大意：

给定序列 \(a_1,a_2...a_n\)，重复如下操作直至序列中只剩 \(2\) 个数

1. 选择连续的三个数 \(a_{i-1},a_i,a_{i+1}\)

2. 给 \(a_{i-1},a_{i+1}\) 的值加上 \(a_i\) 并删去数 \(a_i\)

求最后留下的两个数的和的最小值

\(2 \leq n \leq 18,0 \leq a_i \leq 10^9\)

解题过程：

发现左右端点永远不会被删且其值只被算了一次，最后被删的数的值被算了 \(2\) 次。

则考虑一段左右端点在删完中间点之前不会被删的区间，设 \(p(i)\) 表示 \(a_i\) 的值被算的次数。

则易证 \(p(last)=p(l)+p(r)\)。

此时根据这个式子枚举最后一个被删的点，然后分治再枚举就可以了。（其实就是个搜索

其实我本来想打记忆化，但是数组开不下就打了个没优化的搜索上去，然后就过了...

上代码：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<ctime>
#define int long long
using namespace std;
inline int read()
{
	int kkk=0,x=1;
	char c=getchar();
	while((c<'0' || c>'9') && c!='-')
		c=getchar();
	if(c=='-')
		c=getchar(),x=-1;
	while(c>='0' && c<='9')
		kkk=(kkk<<3)+(kkk<<1)+(c-'0'),c=getchar();
	return kkk*x;
}
int n,a[19];
inline int fun(int l,int r,int nl,int nr)
{
	if(l+1==r)
		return nl*a[l]+nr*a[r];
	int bck=0x7f7f7f7f7f7f7f7f;
	for(register int i=l+1;i<r;++i)
		bck=min(fun(l,i,nl,nl+nr)+fun(i,r,nl+nr,nr)-a[i]*(nl+nr),bck);
	return bck;
}
signed main()
{
	n=read();
	for(register int i=1;i<=n;++i)
		a[i]=read();
	printf("%lld\n",fun(1,n,1,1));
	return 0;
} //异常的短呢...