PAT (Top Level) Practise 1007 Red-black Tree (35)

1007. Red-black Tree (35)

時間限制

150 ms

記憶體限制

65536 kB

代碼長度限制

8000 B

判題程式

Standard

作者

CAO, Peng

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個節點的紅黑樹有多少種。我用的是三維dp

f[i][j][k]表示的是含有i個節點的深度為j的根為k的樹的數量

深度是隻考慮從根節點到葉子節點（不含葉子節點）的黑點數量，k分為0和1,0是紅，1是黑

然後就可以考慮狀态的轉移了，具體看代碼，事實上500個點的紅黑樹深度也不超過8，是以紅黑樹最為二叉平衡樹，本身有嚴格的logn深度，就是實作比較困難。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<stack>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef unsigned long long ull;
typedef long long LL;
const int maxn = 5e2 + 10;
const int mod = 1e9 + 7;
int n;
LL f[maxn][maxn][2], s[maxn][maxn];

void Init()
{
  memset(f, 0, sizeof(f));
  memset(s, 0, sizeof(s));
  f[1][0][0] = f[0][0][1] = 1;
  for (int i = 1; i < maxn; i++)
  {
    for (int j = 1; j <= min(i, 8); j++)
    {
      f[i][j][0] = f[i][j][1] = 0;
      for (int k = 0; k < i; k++)
      {
        (f[i][j][1] += (f[k][j - 1][0] + f[k][j - 1][1]) * (f[i - k - 1][j - 1][0] + f[i - k - 1][j - 1][1]) % mod) %= mod;
        (f[i][j][0] += f[k][j][1] * f[i - k - 1][j][1] % mod) %= mod;
      }
      s[i][j] = (s[i][j - 1] + f[i][j][1]) % mod;
    }
  }
}

int main()
{
  Init();
  while (scanf("%d", &n) != EOF) printf("%d\n", s[n][min(n, 8)]);
  return 0;
}