最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

【全球新视野】洛谷P1040. 加分二叉树

来源:博客园

题目描述

设一个 \(n\) 个节点的二叉树 tree的中序遍历为(\(1,2,3,…,n\)),其中数字 \(1,2,3,…,n\) 为节点编号。

每个节点都有一个分数(均为正整数),记第 \(i\) 个节点的分数为 \(d_i\),tree及它的每个子树都有一个加分,任一棵子树 subtree(也包含 tree本身)的加分计算方法如下:

subtree的左子树的加分 \(×\) subtree的右子树的加分 \(+\) subtree的根的分数


(资料图)

若某个子树为空,规定其加分为 \(1\)。

叶子的加分就是叶节点本身的分数,不考虑它的空子树。

试求一棵符合中序遍历为(\(1,2,3,…,n\))且加分最高的二叉树 tree

要求输出:

(1)tree的最高加分

(2)tree的前序遍历

输入格式

第 \(1\) 行:一个整数 \(n\),为节点个数。

第 \(2\) 行:\(n\) 个用空格隔开的整数,为每个节点的分数(\(0<\)分数\(<100\))。

输出格式

第 \(1\) 行:一个整数,为最高加分(结果不会超过int范围)。

第 \(2\) 行:\(n\) 个用空格隔开的整数,为该树的前序遍历。如果存在多种方案,则输出字典序最小的方案。

解题思路

\(\qquad\)这题初看没有入手点,但是题目有一个特殊的条件:中序遍历是\(1\sim n\)的升序,这也就代表我们可以抽象一下,将这棵树压扁,就可以到一个数轴上,是一个完整的区间\([1,n]\),所以我们可以考虑一下区间\(DP\)。

状态表示

\[用f(l,r)表示数轴上区间[l,r]的最大加分\]

状态计算

\(\qquad\)一个区间的切割方法就是:对于区间\(f[l,r]\),我们在这个子树上假设它的根节点是\(k\),那么在\(k\)左边的区间都是以\(k\)为根的二叉树的左子,右边区间同理。所以对于以\(k\)为根的树,左子为\([l,k-1]\),右子为\([k+1,r]\),根据题目的加分规则,那$$\large score_{tree} = score_{left}\times score_{right} + w_{root}$$

\(\qquad\)此外还要注意,因为二叉树允许没有左子或者没有右子,因此\(k\)应该在\([l,r]\)而非\([l+1,r-1]\)枚举,并且对于\(l=k\)的情况,\(score_{left}=1\),右子同理。

状态统计

\(\qquad\)由于题目需要输出二叉树的前序遍历,所以我们在\(DP\)的时候要保存一些信息。

补充:二叉树的前序遍历,先输出根,再递归左子,再递归右子。

\(\qquad\)对于这个最大方案的根,我们可以在\(DP\)的过程中顺便保存让\([l,r]\)区间加分最大的根节点\(g[l,r]\),为了让字典序最小,我们让断点\(k\)从左向右扫描,遇到更大的值就要\(f[]和g[]\)一起更新,当值相同的时候,以\(k\)越小越好。

然后在输出的时候递归处理:

void print(int l, int r) {    if (l > r) return ; // 不构成节点    int k = g[l][r]; // 根节点     printf("%d ", k);    print(l, k - 1), print(k + 1, r); // 分别递归左右子}

代码

会贴两份,递推\(DP\)和记忆化搜索

递推DP

#include #include #include using namespace std;const int N = 50;int f[N][N], g[N][N], n, w[N];void print(int l, int r) {    if (l > r) return ; // 不构成节点    int k = g[l][r]; // 根节点     printf("%d ", k);    print(l, k - 1), print(k + 1, r); // 分别递归左右子}int main() {    scanf("%d", &n);        for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);        memset(f, 0xcf, sizeof f);    for (int i = 1; i <= n; i ++ )         g[i][i] = i, f[i][i] = w[i]; // 长度为1的叶子节点分数和根的初始化        for (int len = 2; len <= n; len ++ ) //长度为1的初始化过了,从2开始    {        for (int l = 1, r = l + len - 1; r <= n; l ++, r ++ ) //枚举左端点和右端点        {            for (int k = l; k <= r; k ++ ) // 枚举断点            {                int &v = f[l][r], u, L, R;                L = (k == l) ? 1 : f[l][k - 1]; // 如果k == l代表没有左子树,左分数为1                R = (k == r) ? 1 : f[k + 1][r]; // 如果k == r代表没有右子树                u = L * R + w[k]; // 分数计算                if (u > v) v = u, g[l][r] = k; // 更新信息            }        }    }        printf("%d\n", f[1][n]);    print(1, n);        return 0;}

记忆化搜索

#include #include #include using namespace std;const int N = 50;int w[N], f[N][N], g[N][N], n;int dp(int l, int r) {    int &v = f[l][r];    if (~v) return v; // 算过的直接调用    if (l == r) return g[l][r] = l, f[l][r] = w[l]; // 叶子节点的处理        for (int k = l; k <= r; k ++ )     {        int u, L, R;        L = (k == l) ? 1 : dp(l, k - 1); // 如果k == l代表没有左子树,左分数为1        R = (k == r) ? 1 : dp(k + 1, r); // 右子同理        u = L * R + w[k];        if (u > v) g[l][r] = k, v = u;    }        return v;}void print(int l, int r) {    if (l > r) return ;    int k = g[l][r];    printf("%d ", k);    print(l, k - 1), print(k + 1, r);}int main() {    scanf("%d", &n);        for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);        memset(f, -1, sizeof f);    printf("%d\n", dp(1, n));    print(1, n);        return 0;}

关键词: 输入格式 输出格式