BZOJ 3227: [Sdoi2008]紅黑樹(tree)

題目

　　紅黑樹是一類特殊的二叉搜尋樹，其中每個結點被染成紅色或黑色。若将二叉搜尋樹結點中的空指針看作是指向一個空結點，則稱這類空結點為二叉搜尋樹的前端結點。并規定所有前端結點的高度為-1。

　　一棵紅黑樹是滿足下面“紅黑性質”的染色二叉搜尋樹：

　　(1) 每個結點被染成紅色或黑色；

　　(2) 每個前端結點為黑色結點；

　　(3) 任一紅結點的子結點均為黑結點；

　　(4) 在從任一結點到其子孫前端結點的所有路徑上具有相同的黑結點數。

　　從紅黑樹中任一結點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>>;
var
    n,i,j,k,ans:longint;
    f,g:array[-..,..]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)>>,inf);
    filldword(g,sizeof(g)>>,inf);
    //f[0,0]:=0;
    //g[0,0]:=0;
    f[,]:=;
    g[,]:=;
    g[,]:=;
    for i:= to n do
        begin
            for j:= to i do
                begin
                    if <<j>n<< then break;
                    for k:= to i- do
                        begin
                            //f[i,j]:=maxlongint;
                            //g[i,j]:=maxlongint;
                            //writeln('f[',i,',',j,']');
                            f[i,j]:=min(f[i,j],g[k,j-]+g[i-k-,j-]+);
                            g[i,j]:=min(g[i,j],g[k,j-]+g[i-k-,j-]);
                            g[i,j]:=min(g[i,j],f[k,j]+f[i-k-,j]);
                            g[i,j]:=min(g[i,j],f[k,j]+g[i-k-,j-]);
                            //writeln('f[',i,',',j,']=',f[i,j]);
                            //writeln('g[',i,',',j,']=',g[i,j]);
                        end;
                end;
        end;
    ans:=inf;
    for i:= to  do ans:=min(ans,f[n,i]);
    for i:= to  do ans:=min(ans,g[n,i]);
    writeln(ans);
    filldword(f,sizeof(f)>>,-inf);//Warning: range check error while evaluating constants.....JUST IGNORE IT
    filldword(g,sizeof(g)>>,-inf);
    f[,]:=;
    g[,]:=;
    g[,]:=;
    for i:= to n do
        begin
            for j:= to i do
                begin
                    if <<j>n<< then break;
                    for k:= to i- do
                        begin
                            //f[i,j]:=maxlongint;
                            //g[i,j]:=maxlongint;
                            //writeln('f[',i,',',j,']');
                            f[i,j]:=max(f[i,j],g[k,j-]+g[i-k-,j-]+);
                            g[i,j]:=max(g[i,j],g[k,j-]+g[i-k-,j-]);
                            g[i,j]:=max(g[i,j],f[k,j]+f[i-k-,j]);
                            g[i,j]:=max(g[i,j],f[k,j]+g[i-k-,j-]);
                            //writeln('f[',i,',',j,']=',f[i,j]);
                            //writeln('g[',i,',',j,']=',g[i,j]);
                        end;
                end;
        end;
    ans:=-inf;
    for i:= to  do ans:=max(ans,f[n,i]);
    for i:= to  do ans:=max(ans,g[n,i]);
    writeln(ans);
end.