iProblem Link

题目大意

给定 $n$ 个元素，每个元素有 $w,d$ 两个属性，初始第 $i$ 个元素为 $(w_i,0)$，合并元素 $i\to j$ 的代价为 $w_i+d_i+d_j$，合并后形成新元素 $(w_i+w_j,2\max(d_i,d_j)+1)$，求把所有元素合并成一个的最小代价。

数据范围：$n\le 100$。

思路分析

考虑把元素的合并看成一棵二叉树，记每个点 $u$ 子树的最大深度为 $d(u)$，那么所有 $d$ 的贡献就是所有非根节点的 $\sum 2^{d(u)}-1$。

而 $w$ 的贡献可以看成二叉树上每个点选一个子树系数 $+1$，每个叶子的系数就表示该叶子对应 $w_i$ 对答案的贡献系数。

容易发现每个叶子的具体排列不重要，确定二叉树结构后把权值最大的放到系数最小的位置上即可。

因此我们只关心 $n$ 个系数构成的每一种可重集 $C$。

可以暴力 dp，$f_{d,C}$ 表示子树内最大深度为 $d$，构成系数可重集为 $C$ 时，$\sum 2^{d(u)}-1$ 贡献的最小值。

转移时枚举两个状态合并，但这样复杂度太高，无法通过。

我们考虑自上而下地维护这棵二叉树：即从根节点开始，每次把树上的一个叶子分裂出两个儿子节点。

但是每次分裂的时候会影响树上原有节点的 $d(u)$，这就需要记录一些和树形态有关的信息，这是完全不能接受的。

考虑优化，注意到一个子树最大深度为 $d(u)$ 的点，我们可以钦定他在倒数第 $d(u)$ 次操作时才进行第一次分裂，那么此后的每一次分裂他的最大深度都 $+1$，很显然这个过程不改变最优解。

因此存在一种分裂的方式，使得每次分裂后每个非叶节点的最大深度都 $+1$，那么 $\sum 2^{d(u)}$ 就会翻倍，也容易求出分裂后的 $\sum 2^{d(u)}-1$。

但是这么做还不足以通过，首先发现答案不超过 $1.7\times 10^{11}$，可以用来优化 $\sum 2^{d(u)}-1$ 的上界。

其次我们发现按照上述钦定的过程分裂，前一次分裂过的节点的两个儿子中至少有一个这次操作也会分裂，因此每次分裂的节点数单调不降，记录上一次分裂的节点个数即可。

时间复杂度 $\mathcal O(n^2Q_n+nS_n)$，其中 $Q$ 表示叶子数 $1\sim n$ 时的总状态数，$S$ 表示叶子数 $=n$ 时的总状态数，$n=100$ 时 $Q_n=44039,S_n=1745$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll inf=1.7e11;
typedef vector<int> vi;
map <vi,array<ll,2>> f[105];
//[tree size][leaf coef] {min val,low}
ll a[105];
void solve() {
	int n; scanf("%d",&n);
	for(int i=0;i<n;++i) scanf("%lld",&a[i]);
	sort(a,a+n,greater<ll>());
	ll ans=inf;
	for(auto &it:f[n]) {
		const vi&c=it.first;
		ll s=it.second[0];
		for(int i=0;i<n;++i) s+=c[i]*a[i];
		ans=min(ans,s);
	}
	printf("%lld\n",ans);
}
signed main() {
	const int n=100;
	f[1][{0}]={0,1};
	for(int i=1;i<=n;++i) for(auto &it:f[i]) {
		const vi&c=it.first;
		vi d=it.first;
		ll w=it.second[0],lim=it.second[1];
		for(int j=1;j<=i&&i+j<=n;++j) {
			d.insert(upper_bound(d.begin(),d.end(),c[j-1]+1),c[j-1]+1);
			if(j>=lim) {
				ll nw=2*w+(i+j-2);
				if(nw>inf) break;
				if(!f[i+j].count(d)) f[i+j][d]={nw,j};
				else {
					auto &z=f[i+j][d];
					z=min(z,array<ll,2>{nw,j});
				}
			}
		}
	}
	int T; scanf("%d",&T);
	while(T--) solve();
	return 0;
}