题目
红黑树是一类特殊的二叉搜索树，其中每个结点被染成红色或黑色。若将二叉搜索树结点中的空指针看作是指向一个空结点，则称这类空结点为二叉搜索树的前端结点。并规定所有前端结点的高度为-1。
一棵红黑树是满足下面“红黑性质”的染色二叉搜索树：
- 每个结点被染成红色或黑色；
- 每个前端结点为黑色结点；
- 任一红结点的子结点均为黑结点；
- 在从任一结点到其子孙前端结点的所有路径上具有相同的黑结点数。
从红黑树中任一结点x出发(不包括结点x)，到达一个前端结点的任意一条路径上的黑结点个数称为结点x的黑高度，记作bh(x)。红黑树的黑高度定义为其根结点的黑高度。
给定正整数N，试设计一个算法，计算出在所有含有N个结点的红黑树中，红色内结点个数的最小值和最大值。
Input
输入共一个数N。
Output
输出共两行。第一行为红色内结点个数的最小值，第二行为最大值。
Sample Input
8
Sample Output
1
4
HINT
对于 100% 的数据，1≤N≤5000
蒟蒻脑残的自以为是：
首先，实际数据N最大只有2000……不然这个O(N^2*logN)的DP一定会T。
注意题目中的结点数不含前端结点。 以最小值为例，用f[i,j]表示i个结点，黑高度为j的红根树中红色结点最小值，g[i,j]表示i个结点，黑高度为j的黑根树中红色结点最小值。 f[i,j]:=min{g[k,j-1]+g[i-k-1,j-1]+1} (i<=k<=i-2); g[i,j]:=min{g[k,j-1]+g[i-k-1,j-1]),f[k,j]+f[i-k-1,j],f[k,j]+g[i-k-1,j-1]}(i<=k<=i-2); （恕我没有贾大神高超的$\LaTeX$技术） 画画图弄清边界。。。时间i*i*j。
精妙的是红黑树黑高度是有保证的。。。。。也就是j～logN(这样不精确终将酿成大祸) 于是就是O(N^2*logN)了。。。
我的常数极大。。。
filldword就相当于直接对longint赋值了。。注意sizeof要>>2;
const inf=maxlongint>>1;
var
n,i,j,k,ans:longint;
f,g:array[-5..5001,0..30]of longint;
function max(a,b:longint):longint;inline;
begin
if a>b then exit(a);exit(b);
end;
function min(a,b:longint):longint;inline;
begin
if a<b then exit(a);exit(b);
end;
begin
readln(n);
filldword(f,sizeof(f)>>2,inf);
filldword(g,sizeof(g)>>2,inf);
//f[0,0]:=0;
//g[0,0]:=0;
f[1,1]:=1;
g[1,1]:=0;
g[2,1]:=1;
for i:=1 to n do
begin
for j:=1 to i do
begin
if 1<<j>n<<2 then break;
for k:=1 to i-2 do
begin
//f[i,j]:=maxlongint;
//g[i,j]:=maxlongint;
//writeln('f[',i,',',j,']');
f[i,j]:=min(f[i,j],g[k,j-1]+g[i-k-1,j-1]+1);
g[i,j]:=min(g[i,j],g[k,j-1]+g[i-k-1,j-1]);
g[i,j]:=min(g[i,j],f[k,j]+f[i-k-1,j]);
g[i,j]:=min(g[i,j],f[k,j]+g[i-k-1,j-1]);
//writeln('f[',i,',',j,']=',f[i,j]);
//writeln('g[',i,',',j,']=',g[i,j]);
end;
end;
end;
ans:=inf;
for i:=0 to 30 do ans:=min(ans,f[n,i]);
for i:=0 to 30 do ans:=min(ans,g[n,i]);
writeln(ans);
filldword(f,sizeof(f)>>2,-inf);//Warning: range check error while evaluating constants.....JUST IGNORE IT
filldword(g,sizeof(g)>>2,-inf);
f[1,1]:=1;
g[1,1]:=0;
g[2,1]:=1;
for i:=1 to n do
begin
for j:=1 to i do
begin
if 1<<j>n<<2 then break;
for k:=1 to i-2 do
begin
//f[i,j]:=maxlongint;
//g[i,j]:=maxlongint;
//writeln('f[',i,',',j,']');
f[i,j]:=max(f[i,j],g[k,j-1]+g[i-k-1,j-1]+1);
g[i,j]:=max(g[i,j],g[k,j-1]+g[i-k-1,j-1]);
g[i,j]:=max(g[i,j],f[k,j]+f[i-k-1,j]);
g[i,j]:=max(g[i,j],f[k,j]+g[i-k-1,j-1]);
//writeln('f[',i,',',j,']=',f[i,j]);
//writeln('g[',i,',',j,']=',g[i,j]);
end;
end;
end;
ans:=-inf;
for i:=0 to 30 do ans:=max(ans,f[n,i]);
for i:=0 to 30 do ans:=max(ans,g[n,i]);
writeln(ans);
end.