个人认为比较好的（高端）树形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<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
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 6020
int 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<<j > 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
",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<<j > 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
",maxans);
return 0;
}