题目大意
有一个长度为$n$的序列$\{a_i\}$，每次可以选择连续的$3$个数，把中间那个数加到左右两个数上后删除中间那个数。
求最后剩下的两个数的最小值。 $n \leq 18$
分析
我们发现最后的结果肯定是每一个$a_i$乘上一个系数的和，我们考虑倒着$\texttt{dp}$
设$\texttt{f[l][r][x][y]}$表示当前区间的左右端点分别是$l, \; r$，$[l, r]$之间的部分已被删除，$a_l$的系数为$x$，$a_r$的系数为$y$，对整个序列贡献的答案。
那么我们模仿区间$\texttt{dp}$的形式，枚举一个中间点$\texttt{mid} \in (l, r)$则$f[l][r][x][y] = \min\{f[l][mid][x][x+y]+f[mid][r][x+y][y]+a[mid] \times (x+y)\}$
由于$n$不大，直接搜索即可。
代码
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
| #include <bits/stdc++.h>
#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)
ll n, a[50];
ll f(ll l, ll r, ll x, ll y)
{
ll ans = 1e18;
if(r - l <= 1) return 0;
for(int i = l + 1; i <= r - 1; i++)
ans = std::min((f(l, i, x, x + y) + f(i, r, x + y, y) + a[i] * (x + y)), ans);
return ans;
}
int main()
{
scanf("%lld", &n);
for(int i = 1; i <= n; i++)
scanf("%lld", &a[i]);
printf("%lld\n", f(1, n, 1, 1) + a[1] + a[n]);
return 0;
}
|