AGC035D Add and Remove 做题记录

给定一个长 $n$ 的序列 $a$，每次操作可以选择相邻三个元素 $a_{i-1},a_i,a_{i+1}$，将 $a_{i-1}$ 和 $a_{i+1}$ 都加上 $a_i$ 然后删掉 $a_i$。操作完后序列会自动补位，即 $a_{i-1}$ 和 $a_{i+1}$ 会相邻。

最后会剩下两个元素，最小化它们的和。

$2\le n\le 18$，$1\le a_i\le 10^9$。

直接做不好做，考虑时光倒流。

不难发现每个元素最终都会以某个系数算入答案，考虑一次操作本质上是把 $a_{i-1}$ 和 $a_{i+1}$ 的系数都加到 $a_i$ 的上，那么设 $f_{l,r,x,y}$ 表示 $a_l$ 的系数为 $x$，$a_r$ 的系数为 $y$ 时 $a_{[l,r]}$ 的最小贡献，那么有转移：

$f_{l,r,x,y}=\min\limits_{l< k< r}\{f_{l,k,x,x+y}+f_{k,r,x+y,y}-a_k\times (x+y)\}$

减掉是因为重复算了。

这样状态数最多是 $O(n^22^n)$ 的，足以通过本题。

代码如下：

#include <iostream>
#include <cstdio>
#include <map>

using namespace std;

typedef long long ll;

const int S=25;
const ll inf=1e17;

int n,a[S];
map<tuple<int,int,int,int>,ll> f;

ll dfs(int l,int r,int fl,int fr)
{
	if(l+1==r) return 1ll*a[l]*fl+1ll*a[r]*fr; 
	tuple<int,int,int,int> u(l,r,fl,fr);
	if(f.count(u)) return f[u];
	f[u]=inf;
	for(int k=l+1;k<=r-1;k++)
	{
		ll lb=dfs(l,k,fl,fl+fr),rb=dfs(k,r,fl+fr,fr);
		f[u]=min(f[u],lb+rb-1ll*(fl+fr)*a[k]);
	}
	return f[u];
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	printf("%lld\n",dfs(1,n,1,1));
	return 0;
}