牛客练习赛39 B:选点(二叉树遍历+LIS)
发布日期:2022-04-01 13:25:20
浏览次数:26
分类:博客文章
本文共 1187 字,大约阅读时间需要 3 分钟。
链接:
来源:牛客网
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 131072K,其他语言262144K64bit IO Format: %lld题目描述
有一棵n个节点的二叉树,1为根节点,每个节点有一个值 。现在要选出尽量多的点。
对于任意一棵子树,都要满足:
如果选了根节点的话,在这棵子树内选的其他的点都要比根节点的值大;
如果在左子树选了一个点,在右子树中选的其他点要比它小。
输入描述:
第一行一个整数n。第二行n个整数 ,表示每个点的权值。
接下来 行,每行两个整数 。第 行表示第 个节点的左右儿子节点。没有为 。输出描述:
一行一个整数表示答案。
输入
51 5 4 2 33 24 50 00 00 0
输出
3
Solve
题目要求选出来的点满足:左儿子权值>右儿子权值>父亲权值。对二叉树进行后续遍历,可以得到左儿子->右儿子->父亲
的排列,然后对遍历得到的结果反向求LIS即可
Code
#include#define ll long long#define ull unsigned long long#define ms(a,b) memset(a,b,sizeof(a))#define INF 0x7f7f7f7fconst int maxn=1e5+10;const int mod=1e9+7;using namespace std;int w[maxn];int arr[maxn];int ar[maxn];int dp[maxn];struct wzy{ int l,r;}p[maxn];int cnt;void get_arr(int x){ if(p[x].l) get_arr(p[x].l); if(p[x].r) get_arr(p[x].r); arr[cnt++]=w[x];}int main(int argc, char const *argv[]){ ios::sync_with_stdio(false); cin.tie(0); ms(p,0); int n,a,b; cin>>n; for(int i=1;i<=n;i++) cin>>w[i]; for(int i=1;i<=n;i++) { cin>>a>>b; p[i].l=a; p[i].r=b; } get_arr(1); for(int i=0;i
转载地址:https://www.cnblogs.com/Friends-A/p/11054971.html 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年03月30日 17时37分27秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
【多线程与高并发】线程的优先级是怎么回事?
2019-04-26
【多线程与高并发】Java守护线程是什么?什么是Java的守护线程?
2019-04-26
【Leetcode刷题篇/面试篇】-前缀树(Trie)
2019-04-26
【Leetcode刷题篇】leetcode337 打家劫舍III
2019-04-26
【Leetcode刷题篇】leetcode4 寻找两个正序数组的中位数
2019-04-26
【Leetcode刷题篇】leetcode316 去除重复字母
2019-04-26
【Leetcode刷题篇】leetcode1081 不同字符的最小子序列
2019-04-26
【面试篇】Java网络编程与IO流体系
2019-04-26
【Leetcode刷题篇】leetcode84 柱状图中最大的矩形
2019-04-26
【Leetcode刷题篇】leetcode85 最大矩形
2019-04-26
【Leetcode刷题篇】leetcode124 二叉树中的最大路径和
2019-04-26
【Leetcode刷题篇】leetcode297 二叉树的序列化与反序列化
2021-06-29
【Leetcode刷题篇】leetcode301 删除无效的括号
2021-06-29
【Leetcode刷题篇】leetcode239 滑动窗口最大值
2021-06-29
【Leetcode刷题篇】leetcode76 最小覆盖子串
2021-06-29
【Leetcode刷题篇】leetcode10 正则表达式匹配
2021-06-29
【Leetcode刷题篇】leetcode32 最长有效括号
2021-06-29
【Leetcode刷题篇】leetcode128 最长连续序列
2021-06-29
【Leetcode刷题篇】leetcode72 编辑距离
2021-06-29
【Leetcode刷题篇】leetcode312 戳气球
2021-06-29