测评链接
题目大意：
给定序列$a_1,a_2…a_n$，重复如下操作直至序列中只剩2个数。
选择连续的三个数$a_{i-1},a_i,a_{i+1}。$
给$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)$。
此时根据这个式子枚举最后一个被删的点，然后分治再枚举就可以了。（其实就是个搜索
其实我本来想打记忆化，但是数组开不下就打了个没优化的搜索上去，然后就过了…
上代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #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;
}
|