本文共 1150 字,大约阅读时间需要 3 分钟。
【选点】
链接:
来源:牛客网时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 131072K,其他语言262144K 64bit IO Format: %lld有一棵n个节点的二叉树,1为根节点,每个节点有一个值wi。现在要选出尽量多的点。
对于任意一棵子树,都要满足:
如果选了根节点的话,在这棵子树内选的其他的点都要比根节点的值大;
如果在左子树选了一个点,在右子树中选的其他点要比它小。
第一行一个整数n。
第二行n个整数wi,表示每个点的权值。
接下来n行,每行两个整数a,b。第i+2行表示第i个节点的左右儿子节点。没有为0。
n,a,b≤105,−2×109≤wi≤2×109n,a,b≤105,−2×109≤wi≤2×109
一行一个整数表示答案。
51 5 4 2 33 24 50 00 00 0
3
【题解】
实不相瞒,我题都(kan)看(le)不(ban)懂(tian)。
题意:给定每个节点的权值和每个节点的左右儿子(为0即没有儿子),输出最多可选定的点。要求选择时权值满足:根节点<右节点<左节点。
思路:因为要求根节点<右节点<左节点,所以按照先根,再右子树,再左子树的顺序dfs整棵树(相当于二叉树先序遍历),求出dfs序,再在dfs序上求最长上升子序列。复杂度O(nlogn)。
【代码】
#includeusing namespace std;const int maxn=100005;int w[maxn],lson[maxn],rson[maxn];int q[maxn],f[maxn];int tot;void dfs(int u){ if(!u) return; q[++tot]=u; dfs(rson[u]); dfs(lson[u]);}int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;++i) scanf("%d",&w[i]); for(int i=1;i<=n;++i) scanf("%d%d",&lson[i],&rson[i]); dfs(1); //求dfs序 for(int i=1;i<=n;++i) q[i]=w[q[i]]; int cnt=1; f[1]=q[1]; for(int i=2;i<=n;++i) { if(q[i]>f[cnt]) f[++cnt]=q[i]; else { int pos=lower_bound(f+1,f+cnt+1,q[i])-f; f[pos]=q[i]; } } printf("%d",cnt); return 0;}
转载地址:http://kbben.baihongyu.com/