【树型DP】加分二叉树

缺乏、安全感 2021-12-23 12:57 198阅读 0赞

### 问题 b: 【树型DP】加分二叉树 ###

时间限制: 1 Sec  内存限制: 64 MB  
提交: 8  解决: 6  
\[[提交][Link 1]\] \[[状态][Link 2]\] \[[讨论版][Link 3]\] \[命题人:[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

[Link 1]: http://icpc.upc.edu.cn/submitpage.php?cid=1429&pid=27&langmask=262132
[Link 2]: http://icpc.upc.edu.cn/problemstatus.php?id=2340
[Link 3]: http://icpc.upc.edu.cn/bbs.php?pid=2340&cid=1429
[admin]: http://icpc.upc.edu.cn/userinfo.php?user=admin