洛谷題目鏈接:加分二叉樹

題目描述

設(shè)一個n個節(jié)點的二叉樹tree的中序遍歷為（1,2,3,…,n），其中數(shù)字1,2,3,…,n為節(jié)點編號。每個節(jié)點都有一個分數(shù)（均為正整數(shù)），記第i個節(jié)點的分數(shù)為di，tree及它的每個子樹都有一個加分，任一棵子樹subtree（也包含tree本身）的加分計算方法如下：

subtree的左子樹的加分× subtree的右子樹的加分＋subtree的根的分數(shù)。

若某個子樹為空，規(guī)定其加分為1，葉子的加分就是葉節(jié)點本身的分數(shù)。不考慮它的空子樹。

試求一棵符合中序遍歷為（1,2,3,…,n）且加分最高的二叉樹tree。要求輸出；

（1）tree的最高加分

（2）tree的前序遍歷

輸入輸出格式

輸入格式：

第1行：一個整數(shù)n（n＜30），為節(jié)點個數(shù)。

第2行：n個用空格隔開的整數(shù)，為每個節(jié)點的分數(shù)（分數(shù)＜100）。

輸出格式：

第1行：一個整數(shù)，為最高加分（結(jié)果不會超過4,000,000,000）。

第2行：n個用空格隔開的整數(shù)，為該樹的前序遍歷。

輸入輸出樣例

輸入樣例#1：

5
5 7 1 2 10

輸出樣例#1：

145
3 1 2 4 5

一句話題意: 給出一個顆樹,規(guī)定了它的中序遍歷結(jié)果為\(1\)到\(n\),選定一個下標(biāo)為\(i\)的元素,得到的價值為\(val_{(1,i-1)}*val_{(i+1,n)}+w_i\).問總共可以得到的最大價值(可以好好想一想這個計算過程是為什么).

題解: 仔細想一下題意,會發(fā)現(xiàn)這東西和樹并沒有什么關(guān)系.顯然我們可以根據(jù)這個計算價值的方式直接遞歸求解.

然而這樣的復(fù)雜度是\(O(n!)\)的,所以我們需要考慮一下優(yōu)化.

我們可以在遞歸過程中加一個記憶化,同時在更新的時候也記錄一下這個區(qū)間的選定的點.

最后記得要開long long.

#include<bits/stdc++.h> using namespace std; const int N=30+5; const int inf=2147483647; typedef long long lol;lol n, a[N], pre[N][N], f[N][N];lol solve(lol l,lol r){//遞歸求解過程lol res = -inf, temp;if(f[l][r]) return f[l][r];//記憶化if(l > r) return 1;if(l == r) return a[l];for(lol i=l;i<=r;i++){temp = solve(l,i-1)*solve(i+1,r)+a[i];if(temp > res) res = temp, pre[l][r] = i;//取最大值,并記錄區(qū)間選定點.}return f[l][r] = res; }void out(lol l,lol r){if(l > r) return;if(l == r){ printf("%lld ",l); return;}printf("%lld ",pre[l][r]);out(l,pre[l][r]-1);out(pre[l][r]+1,r); }int main(){//freopen("data.in","r",stdin);cin >> n;for(lol i=1;i<=n;i++) cin >> a[i];printf("%lld\n",solve(1,n));out(1,n); printf("\n");return 0; }

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

總結(jié)

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

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