P5566 [SDOI2008]红黑树 贪心|动态规划

题意：

求一颗 n n n个节点的红黑树红色节点数目最多和最少

红黑树是满足如下性质的的染色二叉搜索树：

1. 每个结点被染成红色或黑色；
2. 每个前端结点为黑色结点；
3. 任一红结点的子结点均为黑结点；
4. 在从任一结点到其子孙前端结点的所有路径上具有相同的黑结点数。
5. 二叉搜索树结点中的空指针看作是指向一个空结点，则称这类空结点为二叉搜索树的前端结点。并规定所有前端结点的高度为 -1。

范围&性质： 1 ≤ n ≤ 5000 1\le n\le 5000 1≤n≤5000

分析：

• 贪心

首先对于一颗 n n n个点的红黑树，他必定存在且仅存在 n + 1 n+1 n+1个前端节点，我们构造红黑树的过程可以看做，用这 n + 1 n+1 n+1个前端节点反向递推到根节点的过程

由于前端节点的颜色全是黑色，所以我们考虑一堆黑色的叶子结点向上递推的过程，由上面的性质3,4我们可以推出以下几种情况：

1. 两个黑点变成一个黑点
2. 三个黑点变成一个红点一个黑点
3. 四个黑点变成一个黑点和两个红点
4. 五个黑点变成两个黑点一个红点

这里有一张图，其中最下面一层黑色节点可以看做是前端节点（来源网上，侵删）

对于红色节点最少的情况我们按照两个黑点一组的情况去反向递推，这样每次操作得到的红色节点最少

对于红色节点最多的情况我们按照四个黑点一组的情况去合并，这样每次操作得到的红色节点最多

• 动态规划（以后填坑，下次一定）

代码：

• 贪心：

#include<bits/stdc++.h>

using namespace std;

namespace zzc
{
	int n,ans,m;
	
	void work()
	{
		scanf("%d",&n);
		m=n+1;
		while(m>1)
		{
			ans+=m&1;
			m>>=1;
		}
		printf("%d\n",ans);
		m=n+1;ans=0;
		while(m>1)
		{
			if(m==2) ans++,m--;
			else if((m&3)==1) ans+=((m>>2)<<1)-1,m>>=2,m++;
			else if((m&3)==2) ans+=((m>>2)<<1),m>>=2,m++;
			else if((m&3)==3) ans+=((m>>2)<<1)+1,m>>=2,m++;
			else ans+=(m>>1),m>>=2;
		 } 
		 printf("%d\n",ans);
	}
	
}

int main()
{
	zzc::work();
	return 0;
}