为了避免这个尴尬的话题，小R决定给小Y做一道题。
有一个长度为n的正整数数组A，满足艾> =艾+ 1，现在构造一个数组B，令的Bi = ΣA[j] (j∈[i,n])。
现在，有一个N * N的网格图，左下角坐标是（1,1），右上角坐标是（N，N）。有一个小SB正在坐标为（n，1）的位置，每一时刻，如果他现在在（x，y），他可以选择走到（x?-1，y + 1）或者（x， + 1）div 2），如果选择后者，他要支付Bx的代价。
现在他想走到（1，1），你可以告诉他他支付的代价最少是多少吗？注意在任何时候他都不能离开这个网格图。
因为我不是萝莉控所以这道题我开始并没有做出来
好的先来做50分做法，我们搞一个dp，f[i][j]表示走到i,j的代价
随便搞一下转移:f[i][j]->f[i-1][j+1],f[i][j]+b[i]->f[i][(j+1)/2]
好的接下来讲一些不太相关的东西：
哈夫曼树
这种东西相信大家都应该知道怎么快速构建，一个堆就好了
but这个东西有一种非常鬼畜的解法
我们还是用dp，先将所有的数字从大到小排序
令f[i][j]表示当前的树已经选入了i个数，还有j个空位的状态
那么我们考虑两种转移
1.在空位插入第i+1个数，那么代价就是d*a[i+1]
2.将所有的空位建立2子节点（因为要符合哈夫曼树的性质），代价为0
发现这样需要多一个状态d，非常不好，我们将转移改成以下形式
1.在空位插入第i+1个数，代价为0
2.将所有的空位建立2子节点（因为要符合哈夫曼树的性质），代价为Σa[i+1..n]
容易发现二者等价
写成方程式看看？
f[i][j]->f[i+1][j-1]
f[i][j]->f[i][j*2]+Σa[i+1..n]
发现和上面那个问题的形式是一样的
做完了，两者等价，所以答案就是A的哈夫曼树树根权值
#include<queue>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int T,n; long long ans=0;
priority_queue<int,vector<int>,greater<int> > q;
int _18520(){
scanf("%d",&n); ans=0;
for(int x,i=1;i<=n;++i){
scanf("%d",&x);
q.push(x);
}
for(int x,i=n;i>1;--i){
x=q.top(); q.pop();
x+=q.top(); q.pop();
q.push(x); ans+=x;
}
printf("%lld
",ans); q.pop();
}
int main(){
for(scanf("%d",&T);T--;_18520());
}