【NOI2023】合并书本

Description

传送门

Solution

Part 1

考虑一棵合并树，令 \(ls_u,rs_u\) 表示 \(u\) 的左右儿子，\(d_u\) 表示 \(u\) 子树的最大深度，\(c_u\) 表示 \(u\) 被合并的次数，令所有非叶非根节点对应 \(2^d - 1\) 的和为 \(S\)，则答案为 \(\sum_{i=1}^n c_iw_i + S\)。

可以发现，我们只关心 \(c\) 的可重集及其对应的 \(\min\{S\}\)。当确定 \(c\) 的可重集后，为最小化 \(\sum_{i=1}^n c_iw_i\)，我们将 \(c\) 从小到大排序，\(w\) 从大到小排序，再一一对应即可。

下面，我们的目标是：求出所有可能作为最优解的可重集 \(c\) 及其对应的 \(\min\{S\}\)。

Part 2

先考虑怎么暴力求出所有的可重集 \(c\) 及其对应的 \(\min\{S\}\)。

考虑使用分裂叶子的方法。具体来说，刚开始树上只含一个点，即根，其 \(c = 0\)。每次，我们找到树上的某个叶子 \(u\)，建出 \(ls_u,rs_u\)，\(u\) 不再是叶子的同时得到两个新的叶子。

但是，每当分裂一个叶子后，新的 \(\min\{S\}\) 与树形态有关，难以进一步优化。

考虑一种特殊的分裂顺序，倒序枚举 \(d_0 = n, n - 1, \cdots, 0\)，每次将树上所有 \(d = d_0\) 的点分裂。这样的好处在于，分裂前所有非叶节点、被分裂的叶子的 \(d\) 在分裂后均恰好增加 \(1\)，即 \(\min'\{S\} = 2\min\{S\} \ +\) 分裂前树上非叶点数 \(+\) 分裂叶子数，该值与树形态无关。

设计 \(dp_{c}\) 表示，目前分裂得到的可重集为 \(\{c\}\)，此时 \(\min\{S\}\) 的值。转移时，分裂任何叶子都是可行的，可以忽略 \(d = d_0\) 的限制；这是因为，不满足限制只会将答案算大，而存在最优解因满足限制而被计入。

显然，我们不需枚举所有叶子的集合，只需枚举 \(c\) 的所有前缀，将其分裂并转移。注意，分裂 \(x\) 会得到 \(x, x + 1\)。

期望得分 \(75\) 分。

Part 3

考虑减枝。对于每个 \(\{c\}\)，我们额外记录 \(lim_c\)，表示所有转移到 \(c\) 的最优状态里，至少分裂了多少叶子。那么，此时分裂的叶子数 \(\ge lim_{c}\)。

这样一来，分裂叶子数的可能情况大幅减少，转移复杂度大幅降低，可以通过本题。

Code

参考了 Alex_Wei 的实现。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=105,inf=1e18,max_ans=169073741990;

namespace IO{
	inline char nc(){
		static char buf[500001],*p1=buf,*p2=buf;
		return p1==p2&&(p2=(p1=buf)+fread(buf,1,500000,stdin),p1==p2)?EOF:*p1++;
	}
	char out[500001],*pout=out,*eout=out+500000;
	template<typename T> inline T read(){
		char ch=nc(); T sum=0; bool f=false;
		for(;ch<'0'||ch>'9';ch=nc()) if(ch=='-') f=1;
		while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
		return f?-sum:sum;
	}
}
#define read IO::read<int>

int n,w[N]; map<vector<int>,pair<int,int>> states[N];
void init(int maxsz){
	states[1][{0}]=make_pair(0,1);
	for (int n=1;n<=maxsz;n++){
		for (auto &cur:states[n]){
			int cur_cost=cur.second.first;
			for (int cnt=cur.second.second;cnt<=n&&n+cnt<=maxsz;cnt++){
				int new_n=n+cnt,new_cost=(cur_cost<<1)+cnt+(n-2);
				if (new_cost>max_ans)  break;

				vector<int> new_arr=cur.first;
				for (int i=0;i<cnt;i++)  new_arr.emplace_back(cur.first[i]+1);
				sort(new_arr.begin(),new_arr.end());

				auto it=states[new_n].find(new_arr);
				if (it!=states[new_n].end()){
					auto &info=it->second;
					if (new_cost<info.first)  info=make_pair(new_cost,cnt);
					else if (new_cost==info.first)  info.second=min(info.second,cnt);
				}
				else states[new_n][new_arr]=make_pair(new_cost,cnt);
			}
		}
	}
}
signed main(){
	int T=read(); init(N-5);
	while (T--){
		n=read();
		for (int i=0;i<n;i++)  w[i]=read();
		sort(w,w+n,greater<int>());

		int ans=inf;
		for (auto &state:states[n]){
			int sum=state.second.first;
			for (int i=0;i<n&&sum<ans;i++)  sum+=w[i]*state.first[i];
			ans=min(ans,sum);
		}
		printf("%lld\n",ans);
	}
	return 0;
}