选点

选点

https://ac.nowcoder.com/acm/problem/22494

题意

你有一棵个节点的二叉树,每个节点有权值,你要选尽量多的点,但是得满足以下限制:
对于任意一棵子树,都要满足:
如果选了根节点的话,在这棵子树内选的其他的点都要比根节点的值大;
如果在左子树选了一个点,在右子树中选的其他点要比它小。

分析

根的值右子树的最大值左子树的最大值,如果要选择最多的点,那么如果能够处理出根右子树左子树的序,在序列上维护一个最长上升子序列,就能选到最多的点。答案就是序列长度。

代码

#include<bits/stdc++.h>
#define int long long
const int N=1e6+5,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

int n,tot,cnt;
int w[N],l[N],r[N],a[N],ans[N];

inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

int qpow(int a,int b)
{
    int ans=1;
    while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}
    return ans;
}

void dfs(int x)
{
    if(x==0)    return ;
    a[++tot]=w[x];
    dfs(r[x]);dfs(l[x]);
}

signed main()
{
    n=read();
    for(int i=1;i<=n;i++) w[i]=read();
    for(int i=1;i<=n;i++) l[i]=read(),r[i]=read();
    dfs(1);
    ans[++cnt]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(a[i]>ans[cnt])    ans[++cnt]=a[i];
        else
        {
            int py=upper_bound(ans+1,ans+1+cnt,a[i])-ans;
            ans[py]=a[i];
        }
    }
    printf("%lld",cnt);
    return 0;
}
/*
5
1 5 4 2 3
3 2
4 5
0 0
0 0
0 0 
*/

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-24 07:19
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
7 收藏 评论
分享

全站热榜

正在热议