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;
}