洛谷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)这题初看没有入手点,但是题目有一个特殊的条件:中序遍历是(1sim n)的升序,这也就代表我们可以抽象一下,将这棵树压扁,就可以到一个数轴上,是一个完整的区间([1,n]),所以我们可以考虑一下区间(DP)。
状态表示
状态计算
(qquad)一个区间的切割方法就是:对于区间(f[l,r]),我们在这个子树上假设它的根节点是(k),那么在(k)左边的区间都是以(k)为根的二叉树的左子,右边区间同理。所以对于以(k)为根的树,左子为([l,k-1]),右子为([k+1,r]),根据题目的加分规则,那$$large score_{tree} = score_{left} imes 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 <iostream>
#include <cstring>
#include <algorithm>
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
", f[1][n]);
print(1, n);
return 0;
}
记忆化搜索
#include <iostream>
#include <cstring>
#include <algorithm>
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
", dp(1, n));
print(1, n);
return 0;
}
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击