Description

小Y：“小R 你是蘿莉控嗎。”小R：“...”
為了避免這個(gè)尷尬的話(huà)題，小R 決定給小Y 做一道題。
有一個(gè)長(zhǎng)度為n 的正整數(shù)數(shù)組A，滿(mǎn)足Ai >= Ai+1，現(xiàn)在構(gòu)造一個(gè)數(shù)組B，令Bi =。
現(xiàn)在，有一個(gè)n * n 的網(wǎng)格圖，左下角坐標(biāo)是(1, 1)，右上角坐標(biāo)是(n, n)。有一個(gè)小SB正在坐標(biāo)為(n, 1) 的位置，每一時(shí)刻，如果他現(xiàn)在在(x, y)，他可以選擇走到(x ?-1,y + 1) 或者(x, (y + 1) div 2)，如果選擇后者，他要支付Bx的代價(jià)。
現(xiàn)在他想走到(1, 1)，你可以告訴他他支付的代價(jià)最少是多少嗎？注意在任何時(shí)候他都不能離開(kāi)這個(gè)網(wǎng)格圖。

Input

第一行輸入一個(gè)正整數(shù)T 表示數(shù)據(jù)組數(shù)。
對(duì)于每組數(shù)據(jù)，第一行是一個(gè)整數(shù)n，接下來(lái)一行n 個(gè)整數(shù)表示數(shù)組A。

Output

對(duì)于每組數(shù)據(jù)，輸出一個(gè)整數(shù)表示答案。

Sample Input

1
3
1 1 1

Sample Output

5
樣例解釋：
選擇的路徑可以是：(3， 1)->(2， 2)->(2， 1)->(1， 2)->(1， 1)

Data Constraint

對(duì)于30% 的數(shù)據(jù)，n <= 10
對(duì)于50% 的數(shù)據(jù)，n <=1000
對(duì)于100% 的數(shù)據(jù)，n<= 10^5，1 <= T<= 10，1 <= Ai<= 10^4

?

題解

• 題目大意：當(dāng)前有個(gè)小SB在(n,1)然后他要走到(1,1)，他可以選擇兩種走法，一種是走到(x+1,y-1)不需要代價(jià)，一種是走到(x,(y+1)/2)需要代價(jià)，問(wèn)他需要的最小代價(jià)是多少
• 這種題一眼看到一般就是dp或這是最短路徑問(wèn)題
• 50%：顯然可以用dp來(lái)做，設(shè)f[i][j]為走到(i,j)的最小代價(jià)
• 那么就有兩種轉(zhuǎn)移情況，不過(guò)這dp要倒著做，不然可以考慮跑多幾次
• 100%：數(shù)組是有序的，所以在哈夫曼樹(shù)上深度是遞增不減
• 那么我們可以設(shè)f[i][j]為現(xiàn)在放入了下標(biāo)比 i 小的所有節(jié)點(diǎn)，剩余的葉子節(jié)點(diǎn)有 j 個(gè)
• 按照題目我們就有兩種情況可以走
• ①F[i+1][j?1]，表示在剩下可放的節(jié)點(diǎn)中選一個(gè)來(lái)放第(i+1)個(gè)，不需要代價(jià)
• ②F[i][j?2]+Σa[i+1][n]，表示把剩下的j個(gè)葉子節(jié)點(diǎn)往下再擴(kuò)展2個(gè)節(jié)點(diǎn)，需要為代價(jià)就是后綴和
• 其實(shí)就是50分的dp逆做，然后答案就是哈夫曼樹(shù)的最小權(quán)值
• （其實(shí)這題就是合并果子，合并果子也是哈夫曼樹(shù)求最小權(quán)值）
• 直接用優(yōu)先隊(duì)列做就好了

代碼

1 #include <iostream> 2 #include <queue> 3 #include <cstdio> 4 using namespace std; 5 int T,n; 6 long long ans; 7 priority_queue<int,vector<int>,greater<int> >Q; 8 int main() 9 { 10 scanf("%d",&T); 11 while (T--) 12 { 13 scanf("%d",&n),ans=0; 14 for (int i=1,x;i<=n;i++) scanf("%d",&x),Q.push(x); 15 for (int i=n,x;i>1;i--) x=Q.top(),Q.pop(),x+=Q.top(),Q.pop(),ans+=x,Q.push(x); 16 printf("%lld\n",ans); 17 while (!Q.empty()) Q.pop(); 18 } 19 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Comfortable/p/10299402.html

總結(jié)

以上是生活随笔為你收集整理的[哈夫曼树] Jzoj P4210 我才不是萝莉控呢的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。