题解 AT5141 【[AGC035D] Add and Remove】
starseven
2020-06-12 16:33:26
[AtCoder](https://atcoder.jp/contests/agc035/tasks/agc035_d)
[luogu](https://www.luogu.com.cn/problem/AT5141)
[我的博文](https://www.cnblogs.com/starseven/p/13100304.html)
-----
# 题目大意：
给定一个长度为$N$的序列，每一次可以选择连续的三个数$a_{i-1}$,$a_{i}$,$a_{i+1}$,将其合并变为$a_{i-1}+a_{i}$和$a_{i},a_{i+1}$,依次合并，最后只剩下两个数，求合并后这两个数的和的最小值。
# 输入格式：
$n$
$a_1$ $a_2$ $a_3$ $a_4$ $\dots$ $a_n$
# 思路分析
## 1. 猜测
刚拿到这道题的时候，我看了一下，发现不可做（~~哈哈哈~~）
但是我看了一下数据范围
$$ n \leq 18 $$
然后通过计算器可以算出来
$$ 2^{18}= 262144 $$
$$ 3……{18}=\dots $$
然后可以猜出，$2$的指数级别的可做。
## 2.分析猜测
我在上面为什么要写出2的指数，不是因为其他，就是因为在竞赛里面，这种看着$n$特别小的东西，一般时间复杂度都是指数级别的。
所以我们可以猜测时间复杂度的主流是$2^n$
## 3.分析题目
题目上描述的是将中间删去，再添加到两边去，那么我们可以考虑到说选两个点$l$,$r$,表示在l~r区间中最后留下来的是l&r。
题目上说的是将中间的删去，再添加到两边上去，那么我们可以想到**正难则反**的思想！
我们不考虑第一个删去的是谁，我们考虑最后一个留下的是谁。我们可以分析出为什么要这样想：
因为若是考虑第一个删去的是谁，那删去之后就还有许多不确定的抉择，很难分析，而且无法划分出区间，但是若考虑最后留下 的是谁，那我们就可以清楚的划分出区间，然后左右区间处理就对了。
区间！关键词！
那我们就自然而然想到区间DP
首先，操作可以看做是选择不是两边的一个数，将它删去并把它加到左右两项上
妨考虑倒序考虑整个过程，同时最后的结果一定是每个数乘上一个系数的和。那么最开始，$a_1$和$a_n$的系数都是1
那就可以考虑说设$dp[l][r][x][y]$
表示当前未被删除的数两端是l和r，中间的数已经被删除过了。$a_l$对答案贡献的系数为$x$,$a_r$对答案贡献的系数为$y$。
然后每次转移的时候就是贡献的转移
$$ f[l][r][x][y]=min(f[l][i][x][x+y]+f[i][r][x+y][y]+a[i]\times (x+y)) $$
这样下来的话就是$O(n^3 \times 2^n)$
可是我们完全可以将其改为搜索，然后$n^3$就没有了
$$ the\;small\;but\;strong\;code $$
```cpp
#include<cstdio>
#include<iostream>
#define re register int
#define Starseven main
#define ll long long
using namespace std;
const int N=20;
ll a[N];
ll Dfs(int l,int r,int x,int y){
if(l+1>=r) return 0;
ll ans=100000000000000000;
for(re i=l+1;i<=r-1;i++)
ans=min(ans,Dfs(l,i,x,x+y)+Dfs(i,r,x+y,y)+a[i]*(x+y));
return ans;
}
int Starseven(void){
int n;
cin>>n;
for(re i=1;i<=n;i++) cin>>a[i];
cout<<a[1]+a[n]+Dfs(1,n,1,1)<<endl;
return 0;
}
```