我才不是萝莉控呢

题目大意：

给一个长度为 \(n\) 的数组 \(a\)，满足 $ a_{i} \ge a_{i+1} $，定义 \(b_{i}=\sum\limits_{i=1}^n a_i\)
有一个 \(n\times n\) 的矩形，小 R 现在在 \((n,1)\) 的位置，需要到达 \((1,1)\)。若他在 \(x,y\),他每次可以走到 \((x-1,y+1)\) 或 \((x,\lceil \frac{y}{2}\rfloor)\)。如果选择后者，需要付出 \(b_x\) 的代价。求最小代价。
$ n\le 10^5 $, \(T\) 组数据(\(T\le10\))。

题解

首先考虑一个简单的 dp，\(dp_{i,j}\)表示走到点 \((i,j)\) 的代价。
那么 \(dp_{i,j}\) 可以更新 \(dp_{i-1,j+1}\) 和 \(dp_{i,\lceil\frac{j}{2}\rceil}\)

我们把 dp 反过来写，那么 \(dp_{i,j}=\min(dp_{i+1,j-1},dp_{i,2*j-1}+b_i,dp_{i,2*j}+b_i)\)

根据贪心，\(dp_{i,2*j-1}>dp_{i,2*j}\)。因此方程变为\(dp_{i,j}=\min(dp_{i+1,j-1},dp_{i,2*j}+b_i)\)

我们现在来思考哈夫曼树问题，这个问题除了经典的堆做法以外，还有一种dp做法。不妨把所有数倒序排序，因为我肯定尽量把大的数放在浅层。设一开始就只有一个根节点。定义 \(dp_{i,j}\) 代表目前放置到第 \(i\) 个数字，还有 \(j\) 个空位。然后我现在可以再放一个位置，即转移到 \(dp_{i+1,j-1}\)，也可以给每个空位增加两个儿子，那么后面所有的串的长度代价会加一，也就是 \(dp_{i,2*j}+\sum\limits_{k=i+1}^n a_k\)

仔细比较会发现这两个 dp 式子几乎一样，也就是说，上面问题可以使用哈夫曼树问题的贪心做法。也就是对 a 数组跑合并果子。

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],x,y,t;
long long ans;
priority_queue<int,vector<int>,greater<int> >q;
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		ans=0;
		while(!q.empty())
			q.pop();
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%d",&x),q.push(x);
		while(q.size()>1)
		{
			x=q.top();
			q.pop();
			y=q.top();
			q.pop();
			ans+=x+y;
			q.push(x+y);
		}
		printf("%lld\n",ans);
	}
} 

原文地址：http://www.cnblogs.com/mekoszc/p/16791811.html