https://www.luogu.org/problemnew/show/P1040

題解：這個(gè)題可以用動(dòng)態(tài)規(guī)劃或者記憶化搜索來做。因?yàn)槿绻蠹臃肿畲蟮脑?#xff0c;必須要求它的兒子結(jié)點(diǎn)加分最大，所以就有了最優(yōu)子階段。我們可以枚舉根來更新最大值。中序遍歷有個(gè)特點(diǎn)，在中序遍歷這個(gè)序列上，某個(gè)點(diǎn)左邊的序列一定是這個(gè)點(diǎn)的左子樹，右邊的序列，一定在這個(gè)點(diǎn)的右子樹。root[i,j]表示[i,j]這段序列的根，遞歸輸出先序遍歷。注意初始化，f[i][i]=v[i]，當(dāng)序列只有I一個(gè)元素時(shí)，f[i][i]等于這個(gè)點(diǎn)本身的權(quán)值，當(dāng)l==r-1時(shí)，此時(shí)是空樹設(shè)為1。

C++版本一

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUG #define RI register int using namespace std; typedef long long ll; typedef __int128 lll; const int N=50; const int MOD=1e9+7; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m,k,q; int a[N]; int dp[N][N]; int root[N][N]; int ser(int l,int r){if(dp[l][r]>0)return dp[l][r];if(l==r)return a[l];if(r<l)return 1;for(int i=l;i<=r;i++){int p=ser(l,i-1)*ser(i+1,r)+dp[i][i];if(p>dp[l][r]){dp[l][r]=p;root[l][r]=i;}}return dp[l][r]; } void print(int l,int r){if(r<l)return;if(l==r){printf("%d ",l);return;}printf("%d ",root[l][r]);print(l,root[l][r]-1);print(root[l][r]+1,r); } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifscanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);dp[i][i]=a[i];dp[i][i-1]=1;}printf("%d\n",ser(1,n));print(1,n);//cout << "Hello world!" << endl;return 0; }

C++版本二

#include<iostream> #include<cstdio> using namespace std; int n,v[39],f[47][47],i,j,k,root[49][49]; void print(int l,int r){if(l>r)return;if(l==r){printf("%d ",l);return;}printf("%d ",root[l][r]);print(l,root[l][r]-1);print(root[l][r]+1,r); } int main() {scanf("%d",&n);for( i=1; i<=n; i++) scanf("%d",&v[i]);for(i=1; i<=n; i++) {f[i][i]=v[i];f[i][i-1]=1;}for(i=n; i>=1; i--)for(j=i+1; j<=n; j++)for(k=i; k<=j; k++) {if(f[i][j]<(f[i][k-1]*f[k+1][j]+f[k][k])) {f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k];root[i][j]=k;}}printf("%d\n",f[1][n]);print(1,n);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的加分二叉树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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