正題

---

題目大意

從$(n,1)$到$(1,1)$，一個數組$A$，滿足$A_i\ge A_i+1$
每次有兩個選擇走到$(x?1,y+1)$，或$(x,?y/2?)$。后者需要消耗${\sum }_{i=x}^n{A}_i$的代價
求最小代價

---

解題思路

先預處理好$B_x={\sum }_{i=x}^n{A}_i$
很容易推出動態轉移方程
$$f_{i,j}=min\{f_{i?1,j+1},f_{i,j?2}+B_i\}$$
然后我們發現首先$A_i$是有序的，而$B_i$的性質
設$f_{i,j}$表示放入了前$i$個葉子節點，有$j$個空位的哈夫曼樹權值。
然后每次可以加入一個葉子節點在該層，且以后合并代價增加$A_i$
也可以將兩個合并到新一層，空位多一些。
然后就愉快的發現這個的動態轉移和之前的一樣，其實就是哈夫曼樹。
然后每次肯定是優先選擇權值最小的合并，就是合并果子原題。

---

$code$

#include<cstdio> #define ll long long using namespace std; ll a[100010],num,x,n; long long s,u; void up(ll x) {ll t;while (x>1 && a[x]<a[x/2]){t=a[x];a[x]=a[x/2];a[x/2]=t;x/=2;} } void down(ll x) {ll t,y;while (x*2<=num && a[x]>a[x*2] || x*2+1<=num && a[x]>a[x*2+1]){y=x*2;if (x*2+1<=num && a[x*2]>a[x*2+1]) y++;t=a[x];a[x]=a[y];a[y]=t;x=y;} } void insert(ll x) {a[++num]=x;up(num);} int main() {int t;scanf("%lld",&t);while(t--){s=0;scanf("%lld",&n);num=0;for (ll i=1;i<=n;i++){scanf("%lld",&x);insert(x);} while (num>1){u=a[1];a[1]=a[num];num--;down(1);u+=a[1];a[1]=a[num];num--;down(1);s+=u;num++;a[num]=u;up(num);}printf("%lld\n",s);} }

總結

以上是生活随笔為你收集整理的jozj4010-我才不是萝莉控呢【哈夫曼树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。