Codevs 4909 寂寞的堆

2023-12-25 16:18

文章标签 codevs 寂寞 4909

本文主要是介绍Codevs 4909 寂寞的堆，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

4909 寂寞的堆
时间限制: 1 s
空间限制: 8000 KB
题目等级 : 大师 Master
题目描述 Description
堆，是一种神奇的数据结构不寂寞的堆，是一棵满二叉树，其儿子节点的key值都不大于父亲节点的key值久而久之，不寂寞的堆寂寞了，它不满足于自己这无聊又乏味的性质，于是它提出要求，在自己本身性质的基础上，对于堆中任意一个非叶子节点，它的左子树中任意节点的key值都不能大于其右子树任意节点的key值我们称满足上述两个条件的满二叉树为寂寞的堆给定你一棵满二叉树，询问最少修改多少个节点的key值，才能使它变成寂寞的堆
输入描述 Input Description
第一行是层数表示完全二叉树共n层
之后每一行表示该i层所有叶子节点的值
可能有数据稍大推荐开long long
输出描述 Output Description
最小的k值
样例输入 Sample Input
2
2
1 2
样例输出 Sample Output
0
数据范围及提示 Data Size & Hint
dp
n<=18
对于30%的数据 n<=2
对于60%的数据 n<=10

/*
由树用后序遍历搞成序列.
然后求LIS(nlogn). 
*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#define MAXN 200001
#define LL long long
using namespace std;
struct data{LL lc,rc;}tree[MAXN*4];
LL n,s[MAXN],a[MAXN],tot,ans,cut,len,c[MAXN];
LL read()
{LL x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();return x*f;
}
void slove(LL x)
{if(tree[x].lc) slove(tree[x].lc);if(tree[x].rc) slove(tree[x].rc);s[++tot]=a[x];
}
void erfenlis()
{for(LL i=1;i<=tot;i++)if(s[i]>=c[len]) c[++len]=s[i];else{LL p=upper_bound(c+1,c+len+1,s[i])-c;c[p]=s[i];}
}
int main()
{LL x,z;n=read();for(LL i=1;i<=n;i++){for(LL j=1;j<=pow(2,i-1);j++){cut++;a[cut]=read();if(j%2==1) tree[cut/2].lc=cut;else tree[cut/2].rc=cut;}}slove(1);erfenlis();printf("%lld",cut-len);return 0;
}