1007. Red-black Tree

标签： 动态规划 树形结构

---

题目描述

There is a kind of binary tree named red-black tree in the data structure. It has the following 5 properties:

(1) Every node is either red or black.
(2) The root is black.
(3) All the leaves are NULL nodes and are colored black.
(4) Each red node must have 2 black descends （may be NULL）.
(5) All simple paths from any node x to a descendant leaf have the same number of black nodes.

We call a non-NULL node an internal node. From property （5） we can define the black-height of a red-black tree as the number of nodes on the simple path from the root （excluding the root itself） to any NULL leaf （including the NULL leaf）. And we can derive that a red-black tree with black height H has at least 2H-1 internal nodes.

Here comes the question: given a positive N, how many distinct red-black trees are there that consist of exactly N internal nodes?

Input Specification:

Each input file contains one test case which gives a positive integer N (<= 500).

Output Specification:

For each case, print in a line the number of distinct red-black tees with N internal nodes. Since the answer may be very large, output the remainder of it divided by 1000000007 please.

Sample Input:

5

Sample Output:

8

题解

题目大意:给你一颗含有n个节点的红黑树，问有多少种方案数。（如果不知道啥是红黑树，右转百度）

最开始我的想法用dfs+组合数学，因为必须满足高度相等，所以我枚举上一层高度含有多少个黑色和白色节点，用组合数计算，不过其实枚举了很多重复的状态，所以最后T了一个点。
正解是DP：
设f[0/1][i][j]表示高度为i含有j个节点，当前节点为黑色/白色。
其实状态建立好了，转移方程就很明显了：

//当前节点是黑色 
f[0][j][i] += f[0][k][i - 1] * f[0][j - k - 1][i - 1] % p;
f[0][j][i] += (f[0][k][i - 1] * f[1][j - k - 1][i - 1]) * 2 % p;
f[0][j][i] += f[1][k][i - 1] * f[1][j - k - 1][i - 1] % p;
f[0][j][i] %= p;
//红色 
f[1][j][i] += f[0][k][i] * f[0][j - k - 1][i] % p;
f[1][j][i] %= p;

代码

//DP版 
#include<bits/stdc++.h>
#define N 600
#define ll long long
#define p 1000000007
using namespace std;

ll n, h;
ll Log[N], f[2][N][N];

int main()
{
    scanf("%lld", &n);
    Log[1] = 0;
    for(int i = 2; i <= n; i ++) Log[i] = Log[i / 2] + 1;
    h = Log[n] + 2;
    f[0][1][2] = f[1][1][1] = f[0][0][1] = 1;
    for(int i = 2; i <= h; i ++)
        for(int j = 2; j <= n; j ++)
            for(int k = 0; k < j; k ++)
            {
                //当前节点是黑色 
                f[0][j][i] += f[0][k][i - 1] * f[0][j - k - 1][i - 1] % p;
                f[0][j][i] += (f[0][k][i - 1] * f[1][j - k - 1][i - 1]) * 2 % p;
                f[0][j][i] += f[1][k][i - 1] * f[1][j - k - 1][i - 1] % p;
                f[0][j][i] %= p;
                //红色 
                f[1][j][i] += f[0][k][i] * f[0][j - k - 1][i] % p;
                f[1][j][i] %= p;
            }
    ll ans = 0;
    for(int i = 1; i <= h; i ++) ans += f[0][n][i], ans %= p;
    printf("%lld", ans);        
    return 0;
}

//递归版 
#include<bits/stdc++.h>
#define N 1100
#define ll long long
#define p 1000000007
using namespace std;

int n, m;
ll ans = 0;
ll c[N][N], bin[N];

void pre()
{
    bin[0] = 1;
    for(int i = 1; i <= 20; i ++) 
        bin[i] = bin[i - 1] * 2;
    int t = 510;
    for(int i = 0; i <= t; i ++) 
        c[i][i] = c[i][0] = 1;
    for(int i = 1; i <= t; i ++)
        for(int j = 1; j < i; j ++)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % p;
}

void dfs(int b, int d, int D, int x, ll sum)
{
    int cnt = 2 * b; //红色必须有黑节点承担  
    if(x < 0) return;   
    if(d == D - 1)
    {
        ans = ans + sum * c[cnt][x] % p;
        ans %= p;
        return;
    }
    for(int i = 0; i <= cnt; i ++) //枚举红色节点 
    {
        ll q = c[cnt][i];
        dfs(cnt + i, d + 1, D, x - (cnt + 2 * i), sum * q % p);
    }
}

int main()
{
    pre();
        scanf("%d", &n);
    for(int i = 1; i <= 20; i ++)
    {
        if(bin[i] > n) break;
        if(n >= bin[i] - 1 && n <= bin[2 * i] - 1)
           dfs(1, 0, i, n - 1, 1);
    }
    for(int i = 1; i <= 20; i ++)
        if(n == bin[i] - 1) ans ++;
    printf("%lld", ans % p);

    return 0;
}

心得

根据题目性质设计状态，往往可以得到一个不错的状态转移。