[DP记录]AT5141 [AGC035D] Add and Remove
command_block
2021-04-20 16:13:50
**题意** ： 初始时有长度为 $n$ 的序列 $A$ ，多次进行如下操作，知道只剩两个元素 :
- 选择 $2\leq i\leq |A|-1$。
- 令 $A_{i-1},A_{i+1}$ 加上 $A_i$ ，然后将 $A_i$ 从序列中删除。
最小化最后剩下的两个元素的和。
$n\leq 18$ ，时限$\texttt{2s}$。
------------
操作只会影响相邻的元素，联想到区间 DP。
若正着考虑，一次操作后，两侧还能互相影响。
不妨倒着考虑。先考虑最后一次操作，此时有 $A_1,A_2,A_3$ ，删除了 $A_2$。
那么 $A_2$ 会加一次到 $A_1$ ，加一次到 $A_3$ ，贡献系数为 $2$。
考虑之前的情况，形如 $A_1,...S_1...,A_2,...S_2...,A_3$ ，其中 $S_1$ 中的元素，有些贡献到了 $A_1$ ，有些贡献到了 $A_2$ 。$S_2$ 中的元素有些贡献到了 $A_3$ ，有些贡献到了 $A_2$。
这里，两种贡献的系数是不同的，$A_1,A_3$ 的贡献系数是 $1$ ，而 $A_2$ 是 $2$。
于是，可以设计如下 $\rm DP$ ：
设 $dp[l,r][cl,cr]$ 表示删除区间 $[l,r]$ 内的元素，向 $A_{l-1}$ 的贡献的系数为 $cl$ ，向 $A_{r+1}$ 的贡献的系数为 $cr$ ，贡献的最小值。
答案即为 $dp[2,n-1][1,1]+A_1+A_n$。
有如下转移 ：
$$dp[l,r][cl,cr]=\min\limits_{k=l}^rdp[l,k-1][cl,cl+cr]+(cl+cr)A_k+dp[k+1,r][cl+cr,cr]$$
直接进行不记忆化的搜索，复杂度递推式如下 ：
$$T(n)=\sum\limits_{k=1}^nT(k-1)+T(n-k)$$
有上界 $O(2^nn)$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;
int a[20];
ll dfs(int l,int r,int cl,int cr)
{
if (l>r)return 0;
ll ret=1ll<<60;
for (int k=l;k<=r;k++)
ret=min(ret,dfs(l,k-1,cl,cl+cr)+1ll*(cl+cr)*a[k]+dfs(k+1,r,cl+cr,cr));
return ret;
}
int n;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)scanf("%d",&a[i]);
printf("%lld",a[1]+dfs(2,n-1,1,1)+a[n]);
return 0;
}
```