最新要闻
- 电脑故障影响数千架次航班!全美航班停飞限制取消
- 灵动岛只是过渡品!iPhone 16或配备屏下Face ID
- 当前要闻:小米将参加MWC2013:不会发布小米13 Ultra
- 弄疯了无数人的游戏:差点让我砸掉显示器!
- 焦点消息!登录、投屏处处受限!视频平台被指吃相难看 你还开会员吗?
- 热消息:伊利回应30支冰糕分30箱发货 被网友吐槽太浪费:订单推送失误造成
- 全球热点!网友拿到了一加11:真的跟老板说的一样巨流畅
- 144MB缓存游戏神U!AMD锐龙7000X3D定档:情人节大礼
- 【当前热闻】美国所有航班都已停飞 电脑系统竟突发故障:官方给出恢复时间
- 焦点关注:日系首款电动B级轿车!本田雅阁插混版来了:可挂绿牌
- 广州一宝马SUV冲撞人群 官方通报:已致5死13伤 司机被控制
- 环球即时:太阳4天内发出两次X级耀斑:几天后指向地球、或引强烈地磁暴
- 每日聚焦:真我GT Neo5标准版曝光:不到200g机身塞进5000mAh和骁龙8+
- 天天微头条丨I Do钻戒母公司被申请破产:被年轻人摒弃 太不保值 有人1.8万买只值180元
- 新款魏牌拿铁DHT-PHEV亮相惹争议 网友吐槽:不能我一个人瞎
- 头条焦点:小米最好高端口碑!雷军:MIX Fold 2研发成本很高 屏幕是天价定制
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
【全球新视野】洛谷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;}
【全球新视野】洛谷P1040. 加分二叉树
C#、TS和Dart对比2:变量和作用域
电脑故障影响数千架次航班!全美航班停飞限制取消
灵动岛只是过渡品!iPhone 16或配备屏下Face ID
当前要闻:小米将参加MWC2013:不会发布小米13 Ultra
弄疯了无数人的游戏:差点让我砸掉显示器!
焦点消息!登录、投屏处处受限!视频平台被指吃相难看 你还开会员吗?
网址导航
全球看点:P2448 无尽的生命
[概率论与数理统计]笔记:3.3 随机向量的函数的分布与数学期望
世界新资讯:React核心概念与JSX
热消息:伊利回应30支冰糕分30箱发货 被网友吐槽太浪费:订单推送失误造成
全球热点!网友拿到了一加11:真的跟老板说的一样巨流畅
mac下php环境搭建
天天快讯:MQ——如何保证消息不会丢失
144MB缓存游戏神U!AMD锐龙7000X3D定档:情人节大礼
【当前热闻】美国所有航班都已停飞 电脑系统竟突发故障:官方给出恢复时间
速看:偶数位(熟悉二进制)
当前信息:Mysql页分裂
焦点关注:日系首款电动B级轿车!本田雅阁插混版来了:可挂绿牌
广州一宝马SUV冲撞人群 官方通报:已致5死13伤 司机被控制
环球即时:太阳4天内发出两次X级耀斑:几天后指向地球、或引强烈地磁暴
世界视点!02-Sed语法介绍
每日聚焦:真我GT Neo5标准版曝光:不到200g机身塞进5000mAh和骁龙8+
天天微头条丨I Do钻戒母公司被申请破产:被年轻人摒弃 太不保值 有人1.8万买只值180元
新款魏牌拿铁DHT-PHEV亮相惹争议 网友吐槽:不能我一个人瞎
CQOI2007,洛谷P4710涂色
头条焦点:小米最好高端口碑!雷军:MIX Fold 2研发成本很高 屏幕是天价定制
奢侈服装品牌Acne新春广告片被批 网友称其“阴间兔”
男童放鞭炮炸飞井盖连砸两车 科普:炮仗遇上下水道堪比小炸弹
【环球播资讯】男子吐槽APP看天气预报要点8个广告 网友:手机自带的不好吗?
世界快看点丨雅迪参展CES:汽车级快充亮相 20分钟充满80%电池
全球快看点丨链表栈队列递归哈希表有序表
Codeforces 1278 F Cards 增强版 题解 (斯特林数,推式子)
热点在线丨sortablejs 列表拖拽排序,js vue2,解决拖拽排序乱序问题
世界快资讯:用低代码这把“剑”之前,要先看定位,各取所需
当前短讯!开源动物行为分析实验箱(斯金纳箱)研发总结
三星Galaxy S24系列或取消Plus版本:销量太惨淡
【天天时快讯】大碗更尽兴!海福盛香辣牛肉面大促:每桶到手3块钱
今日视点:特斯拉2022年中国销量44万辆 还不敌比亚迪一个宋
《咬文嚼字》公布年度十大语文差错:连花清瘟?莲花清瘟?
世界观焦点:荣耀二代骁龙8新机来了!Magic 5系列入网:春节后发布
环球观速讯丨python之路 58 linux文件配置相关
学习笔记——MyBatis自动映射与自定义映射;Mybatis延迟加载
当前关注:C#、TS和Dart对比1:概述
即时焦点:SpringBoot Xss漏洞修复
软件开发入门教程网之Git 基本操作
热门:别克GL8危险!腾势D9累计订单超5万:50%用户来自BBA
3岁男童反复呕吐被确诊癌症晚期:被称为儿童癌症之王
当前速读:《咬文嚼字》公布2022年度十大语文差错:天和核心舱、莘莘学子上榜
努比亚Z50限定版明天首销:搭载最纯净的定制系统 无广告
环球观点:操作系统
环球播报:C++构造函数【cherno课程学习】
手机端H5 实现自定义拍照界面
今日热议:2022年我国人均存款近1.3万元 网友:又拖后腿了
【报资讯】一家四口在三亚溺水全部遇难:官方科普“离暗流”危险性
天天微动态丨2022收官!合资车时代被终结 “迪王”养成 大票车企失去肥年
【环球速看料】《小美人鱼》真人电影周边童书曝光 黑美人鱼好可爱
天天即时:双形态不入耳!讯飞开放式办公耳机iFLYBUDS Air图赏
小米MIX Fold 2厚度与戴壳iPhone 14 Pro Max相当 雷军:惊艳
当前通讯!3秒复制任何人的嗓音!微软音频版DALL·E细思极恐 连环境背景音也能模仿
每日热议!官宣:Intel发烧U回来了!350W 56核能打过AMD 280W 64核吗?
每日播报!人气爆棚!上美回应《中国奇谭》周边断货:已开足马力生产
Shell 命令奇淫技巧,就是有点短
当前头条:你买过哪些?苹果已售出23.2亿部手机 国人最爱iPhone 6
每日速递:美国加州风暴天气已致17死 有大树直接被连根拔起
环球速看:取消灵动岛!苹果iPhone 16 Pro将配备屏下Face ID
春运咋办?博主跑1千公里高速实测充电桩:有服务区一半都是坏的
【时快讯】《中国奇谭》口碑封神!仅上线三集 播放量突破5000万
【世界聚看点】CPU、显卡持续涨价!全球PC出货量暴跌 联想继续第一
简讯:(五)elasticsearch 源码之查询流程分析
环球热文:消息服务 + Serverless 函数计算如何助力企业降本提效?
世界滚动:el-table更新数据页面闪烁问题
全球今日报丨DJI这三个字母 是怎么占领你的背包的
环球热头条丨告别毛巾“一条恒久远”!金号纯棉抑菌毛巾大促:一条5块钱
今日快讯:哪吒汽车联手宁德时代共研“滑板底盘”:电池、底盘合体
世界信息:苹果加大降低中国工厂依赖程度:都要搬走?印度成香饽饽 出口激增
独占4K AMR 120帧高规格!《流浪地球2》发布CINITY海报
世界热点!指针知识点总结
每日热讯!TiDB 底层存储结构 LSM 树原理介绍
linux基础:2、前期必备知识、系统运行命令、快捷方式命令、目录结构相关命令、文件与文件夹相关命令、目录结构
环球今日报丨C# 循环给多个连续编号的控件赋值
网上银行怎么转账?网上银行转账限额是多少?
诺基亚5800xm当年多少钱?诺基亚5800XM手机参数
投影仪吊架怎么安装?吊式投影仪安装方法
华为gt2怎么设置相册表盘?华为gt2有血氧功能吗?
唐门鸟翔碧空在哪里学?唐门鸟翔碧空可以放什么技能?
雷龙鱼水温多少合适?雷龙吃什么饲料?
最新消息:三星Galaxy S23系列定档:2月2日登场 首发新版骁龙8 Gen2
《满江红》公布秦桧版预告:饰演者雷佳音狠辣狡诈
【全球新要闻】特斯拉大降价 其它车企跟不跟?乘联会秘书长发声
焦点速读:万物有灵 被收养流浪狗跳车拦住怀孕主人 下一秒山路塌方
每日聚焦:1208元!中国探月航天推出限量火箭碎片:运送嫦娥四号的长三乙
加减乘除是谁发明的?加减乘除混合运算100道
米亲韩语是什么意思?韩语shake it是什么意思?
全高清和超高清有什么区别?全高清和超高清4K哪个更护眼?
异丙醇的作用与用途有哪些?异丙醇和酒精的区别是什么?
Serverless 奇点已来,下一个十年将驶向何方?
每日热点:没电、没网也能支付 数字人民币全新功能上线:安卓先行
环球微资讯!用上比亚迪发动机 斯威大虎ED-i增程版亮相:油耗低至2.06升