【AtCoder Grand Contest 035 D】Add and Remove

mrsrz 1月 24, 2020

搜索，动态规划。

题目大意：

给定一个序列 $A_1,A_2,\ldots,A_n$，要执行 $n-2$ 次操作，每次：

选定 $i$（$1\lt i\lt$ 序列长度）。
令 $A_{i-1}\leftarrow A_{i-1}+A_i$。
$A_{i+1}\leftarrow A_{i+1}+A_i $。
删除 $A_i$。

最后会剩下两个数，求剩下的两个数之和最小是多少。

题解：

考虑对于区间 $[l,r]$，将其变为两个数的和的最小值。

我们考虑 $A_l,A_r$ 对答案的贡献。

令 $f_{l,r,x,y}$ 表示当前考虑的区间为 $[l,r]$，最边上的元素对答案的贡献的系数为 $x,y$ 时，$(l,r)$ 能得到的最小值。

$f_{l,r,x,y}=\sum_{i=l+1}^{r-1}f_{l,i,x,x+y}+f_{i,r,x+y,y}+(x+y)A_i$

相当于每次枚举最后一次操作的数，并进行合并。

状态数约为 $2^n$，可以直接搜索。

Code：

#include<cstdio>
#include<algorithm>
typedef long long LL;
int A[20],n;
LL f(int l,int r,int x,int y){
    if(r-l<=1)return 0;
    LL p=1e18;
    for(int i=l+1;i<r;++i)
    p=std::min(p,f(l,i,x,x+y)+f(i,r,x+y,y)+(LL)(x+y)*A[i]);
    return p;
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i)scanf("%d",A+i);
    printf("%lld",f(0,n-1,1,1)+*A+A[n-1]);
    return 0;
}