个人认为比较好的（高端）树形DP，也有可能是人傻

3227: [Sdoi2008]红黑树(tree)

Time Limit: 10 Sec Memory Limit: 128 MB

Submit: 158 Solved: 96

[Submit][Status][Discuss]

Description

　　红黑树是一类特殊的二叉搜索树，其中每个结点被染成红色或黑色。若将二叉搜索树结点中的空指针看作是指向一个空结点，则称这类空结点为二叉搜索树的前端结点。并规定所有前端结点的高度为-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

Source

这道题啊，想了很久，也调了挺长时间的；中间请求Claris的帮助，可是Claris说太久没看这道了，记不太清细节了，于是我要了他的代码。。。Claris早期的代码风格不认直视啊我的天！

题解：

令f【i】【j】【0，1】表示 包含i个非前端节点的节点，黑高度为j的，红根/黑根 红黑树中的最小/最大红节点数。

于是得到转移：

f[i][j][0]=min/max(f[i][j][0],f[k][j-1][1]+f[i-k-1][j-1][1]+1);

f[i][j][1]=min/max(f[i][j][1],min/max(f[k][j-1][1]+f[i-k-1][j-1][1],min/max(f[k][j][0]+f[i-k-1][j][0],f[k][j][0]+f[i-k-1][j-1][1])));

然后做好初始化即可；

code：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int read(){    int 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-'0'; ch=getchar();}    return x*f;}#define maxn 6020int n;int f[maxn][32][2];int maxans,minans;int main(){    n=read();    maxans=-0x7fffffff;minans=0x7fffffff;    memset(f,0x3f,sizeof f);    f[1][1][0]=1;f[1][1][1]=0;f[2][1][1]=1;    for (int i=1; i<=n; i++)        for (int j=1; j<=i; j++)            if (1<
          
            n<<2) break; else for (int k=0; k<=i-2; k++) { f[i][j][0]=min(f[i][j][0],f[k][j-1][1]+f[i-k-1][j-1][1]+1); f[i][j][1]=min(f[i][j][1],min(f[k][j-1][1]+f[i-k-1][j-1][1], min(f[k][j][0]+f[i-k-1][j][0],f[k][j][0]+f[i-k-1][j-1][1]))); } for (int i=0; i<=30; i++) minans=min(min(minans,f[n][i][0]),f[n][i][1]); printf("%d\n",minans); memset(f,-0x3f,sizeof f); f[1][1][0]=1;f[1][1][1]=0;f[2][1][1]=1; for (int i=1; i<=n; i++) for (int j=1; j<=i; j++) if (1<
           
             n<<2) break; else for (int k=0; k<=i-2; k++) { f[i][j][0]=max(f[i][j][0],f[k][j-1][1]+f[i-k-1][j-1][1]+1); f[i][j][1]=max(f[i][j][1],max(f[k][j-1][1]+f[i-k-1][j-1][1], max(f[k][j][0]+f[i-k-1][j][0],f[k][j][0]+f[i-k-1][j-1][1]))); } for (int i=0; i<=30; i++) maxans=max(max(maxans,f[n][i][0]),f[n][i][1]); printf("%d\n",maxans); return 0;}