Time Limit:?10 Sec??Memory Limit:?128 MB
Submit:?115??Solved:?20
[Submit][Status][Discuss]

Description

小凸和小方相約玩密室逃脫，這個密室是一棵有n個節點的完全二叉樹，每個節點有一個燈泡。點亮所有燈泡即可逃出密室。每個燈泡有個權值Ai，每條邊有個權值bi。點亮第1個燈泡不需要花費，之后每點亮4個新的燈泡V的花費，等于上一個被點亮的燈泡U到這個點V的距離Du,v，乘以這個點的權值Av。在點燈的過程中，要保證任意時刻所有被點亮的燈泡必須連通，在點亮一個燈泡后必須先點亮其子樹所有燈泡才能點亮其他燈泡。請告訴他們，逃出密室的最少花費是多少。

Input

第1行包含1個數n，代表節點的個數 第2行包含n個數，代表每個節點的權值ai。(i=l，2，…，n) 第3行包含n-l個數，代表每條邊的權值bi，第i號邊是由第(i+1)/2號點連向第i+l號點的邊。 (i=l，2...N-1)

Output

輸出包含1個數，代表最少的花費。

Sample Input

3
5 1 2
2 1

Sample Output

5

HINT

對于100%的數據，1≤N≤2×105，1<Ai,Bi≤10^5

題解：

　　a[x]表示x結點的權值；b[x]表示x結點到其父親的邊權；l[x]表示x的深度，令l[x]==1；d[x]表示x到根的距離；

　　f[x][y]表示走完x及其子樹再走到y的最小代價。考慮轉移方式，如果x是葉子節點，那么答案就是a[y]*distance(x,y)；如果x只有左孩子，就先遍歷左子樹，狀態轉移是a[lc]*b[lc]+f[lc][y]；如果兩個孩子都有，就考慮是先轉移到左孩子還是右孩子，f[x][y]=min(a[lc]*b[lc]+f[lc][rc]+f[rc][y],a[rc]*b[rc]+f[rc][lc]+f[lc][y])。

　　但是考慮到題目數據很大，這樣的轉移肯定在時間和空間上都不行。又發現有的x，y是不合法的，比如y肯定不能是x的子節點。由此考慮有意義的x，y，可以發現，如果x有一個祖先p(p包括x)，則y是p的兄弟節點，f[x][y]的含義變成了走完x及其子樹到深度為y的節點的子節點的最小代價。

　　設g[x][i]表示走完x的子樹再走到x的深度為i的祖先的最小代價。轉移： 葉子：g[x][i]=a[y]*(d[x]-d[y]) 只有左孩子：g[x][i]=g[lc][i]+a[lc]*b[lc] 左右孩子都有：g[x][i]=min(a[lc]*b[lc]+f[lc][l[x]]+g[rc][i],a[rc]*b[rc]+f[rc][l[x]]+g[lc][i])。

　　最后就是統計答案了，我們選定一個節點x作為第一個點亮的燈，然后統計其子樹的答案，再走到x的父節點，再走x的兄弟節點......以此類推。

　　由于f[][]和g[][]的第一維都是n，第二維都是logn，所以總的時間復雜度是O(nlogn)。

?

1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #include<queue> 8 #include<vector> 9 using namespace std; 10 typedef long long LL; 11 const LL maxn=2*1e5+10; 12 LL N,a[maxn],b[maxn],d[maxn],l[maxn]; 13 LL ANS,f[maxn][20],g[maxn][20]; 14 int main(){ 15 // freopen("light.in","r",stdin); 16 // freopen("light.out","w",stdout); 17 scanf("%lld",&N); 18 for(LL i=1;i<=N;i++) scanf("%lld",&a[i]); 19 l[1]=1; 20 for(LL i=2;i<=N;i++){ 21 scanf("%lld",&b[i]); 22 l[i]=l[i>>1]+1; d[i]=d[i>>1]+b[i]; 23 } 24 for(LL x=N,y,lc,rc,i;x;x--){ 25 for(LL i=0;i<l[x];i++){ 26 lc=2*x; rc=lc+1; 27 y=(x>>(l[x]-i-1))^1; 28 if(lc>N) f[x][i]=a[y]*(d[x]+d[y]-d[y>>1]*2); 29 else if(rc>N) f[x][i]=a[lc]*b[lc]+f[lc][i]; 30 else f[x][i]=min(a[lc]*b[lc]+f[lc][l[x]]+f[rc][i], 31 a[rc]*b[rc]+f[rc][l[x]]+f[lc][i]); 32 } 33 } 34 for(LL x=N,y,lc,rc,i;x;x--){ 35 for(LL i=0;i<=l[x];i++){ 36 lc=2*x; rc=lc+1; 37 y=x>>(l[x]-i); 38 if(lc>N) g[x][i]=a[y]*(d[x]-d[y]); 39 else if(rc>N) g[x][i]=g[lc][i]+a[lc]*b[lc]; 40 else g[x][i]=min(a[lc]*b[lc]+f[lc][l[lc]-1]+g[rc][i], 41 a[rc]*b[rc]+f[rc][l[rc]-1]+g[lc][i]);//f[lc][l[lc]-1]表示結點走完lc及子樹再走到rc的最小代價 42 } 43 } 44 ANS=g[1][0]; 45 for(LL i=2;i<=N;i++){ 46 LL res=g[i][l[i]-1]; LL tmp=i; 47 for(LL y,z;tmp!=1;tmp>>=1){ 48 y=tmp^1; z=tmp>>1; 49 if(y>N) res+=a[z>>1]*b[z]; 50 else res+=a[y]*b[y]+g[y][l[z]-1]; 51 } 52 ANS=min(ANS,res); 53 } 54 printf("%lld",ANS); 55 return 0; 56 }

?

?

?

轉載于:https://www.cnblogs.com/CXCXCXC/p/5312237.html

總結

以上是生活随笔為你收集整理的bzoj 4446: [Scoi2015]小凸玩密室的全部內容，希望文章能夠幫你解決所遇到的問題。

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