加分二叉樹

ssl 1033

luogu 1040

題目大意：

有一棵中序遍歷為1,2,3…n的二叉樹（當(dāng)然二叉樹的樣子沒有固定），現(xiàn)在給出每個節(jié)點的分數(shù)，一個節(jié)點的加數(shù)=兩個子節(jié)點的加數(shù)相乘+當(dāng)前節(jié)點的分數(shù)（空的子節(jié)點加數(shù)為1，葉子節(jié)點加數(shù)為它的分數(shù)），現(xiàn)在要你求最大的加數(shù)

輸入樣例

5 5 7 1 2 10

輸出樣例

145 3 1 2 4 5

數(shù)據(jù)范圍

$n<30$
$Ans?4,000,000,000$

解題思路：

設(shè)$f[i][j]$為中序遍歷為i~j的子樹的最大加數(shù)，然后每次枚舉中間點去劃分樹，然后DP即可

代碼：

#include<cstdio> #define max(a,b) (a)>(b)?(a):(b) using namespace std; long long n,a[50],f[50][50],s[50][50]; void dg(long long l,long long r)//遞歸輸出前序遍歷 {if (l>r) return;printf("%lld ",s[l][r]);dg(l,s[l][r]-1);dg(s[l][r]+1,r); } int main() {scanf("%lld",&n);for(int i=1;i<=n;++i){f[i][i-1]=1;//處理空子樹的情況f[i+1][i]=1;scanf("%lld",&a[i]);f[i][i]=a[i];s[i][i]=i; }for(int i=n-1;i>0;--i)//倒著枚舉可以先做小的再做大的for(int j=i+1;j<=n;++j)//枚舉范圍for(int k=i;k<=j;++k)//中間點if (f[i][k-1]*f[k+1][j]+a[k]>f[i][j]){f[i][j]=f[i][k-1]*f[k+1][j]+a[k];//DPs[i][j]=k;}printf("%lld\n",f[1][n]);dg(1,n); }

總結(jié)

以上是生活随笔為你收集整理的【树形区间DP】加分二叉树（ssl 1033/luogu 1040）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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