問題 b: 【樹型DP】加分二叉樹

時間限制: 1 Sec??內存限制: 64 MB
提交: 8??解決: 6
[提交] [狀態] [討論版] [命題人:admin]

題目描述

科技忽略了過程就是魔法，魔法展示了過程就是科技。例如，在魔法世界彪炳史冊的艾薩克·牛頓爵士，就被稱為“最初的科學家，最后的煉金術士”。魔法世界的所謂魔法，其本質就是科技，只不過因為在遠古時代發生的幾次戰亂，導致相當數量尖端科技理論的遺失和殘缺，使得人們只知道如何使用科技卻無法解釋其原理，只好統稱為魔法而已。所以魔法世界的科技樹在宇宙各種文明的發展中，可以抽象的看成一顆奇怪的具有n個節點的二叉樹tree，樹的中序遍歷為（l，2，3，…，n），其中數字1，2，3，…，n為節點編號。每個節點都有一個分數（均為正整數），記第i個節點的分數為di，tree及它的每個子樹都有一個加分，任一棵子樹subtree（也包含tree本身）的加分計算方法如下：?
? ?subtree的左子樹的加分× subtree的右子樹的加分＋subtree的根的分數。
若某個子樹為空，規定其加分為1，葉子的加分就是葉節點本身的分數。不考慮它的空子樹。 試求一棵符合中序遍歷為（1，2，3，…，n）且加分最高的二叉樹tree。要求輸出：?
（1）tree的最高加分。
（2）tree的前序遍歷

?

輸入

第1行：一個整數n（n＜30），為節點個數。 第2行：n個用空格隔開的整數，為每個節點的分數（分數＜100）。

?

輸出

第1行：一個整數，為最高加分（結果不會超過4000 000 000）。 第2行：n個用空格隔開的整數，為該樹的前序遍歷。（行尾有一個空格）

?

樣例輸入

復制樣例數據

10 5 4 8 9 19 2 1 40 20 22

樣例輸出

839701 7 4 2 1 3 5 6 9 8 10 #include<bits/stdc++.h> #define REP(i, a, b) for(int i = (a); i <= (b); ++ i) #define REP(j, a, b) for(int j = (a); j <= (b); ++ j) #define PER(i, a, b) for(int i = (a); i >= (b); -- i) using namespace std; const int maxn = 36; template <class T> inline void rd(T &ret) {char c;ret = 0;while ((c = getchar()) < '0' || c > '9');while (c >= '0' && c <= '9') {ret = ret * 10 + (c - '0'), c = getchar();} } int dp[maxn][maxn], t[maxn][maxn], n, p[maxn], tot; int dfs(int l, int r) {if (dp[l][r] > 0)return dp[l][r];if (l > r)return 1;if (l == r) {dp[l][r] = p[l];t[l][r] = l;}else {REP(i, l, r) {int tmp = dfs(l, i - 1)*dfs(i + 1, r) + p[i];if (tmp > dp[l][r]) {dp[l][r] = tmp;t[l][r] = i;}}}return dp[l][r]; } void dfs2(int l, int r) {if (l > r)return;if (!tot)cout << t[l][r];else cout << ' ' << t[l][r];tot++;dfs2(l, t[l][r] - 1);dfs2(t[l][r] + 1, r); } int main() {rd(n);REP(i, 1, n)rd(p[i]);cout << dfs(1, n) << endl;dfs2(1, n);return 0; }

?

轉載于:https://www.cnblogs.com/czy-power/p/10459997.html

總結

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

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