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;
}