Brief description :

计数，有 n 个节点深度为 k 的有根树的数目。

Analyse :

原题的描述是括号序列，不过我们知道括号序列和树结构计数是等价的。。
目前还不知道这个是否同 Catalan 序列有关，先朴素DP一份。

#include 
#include "bignum.h"
using namespace std;
const int N = 50;
const int K = 50;
bignum dp[K+1][N+1][N+1];
// dp[i][l][r] 表示，当前最大深度为 i ，且有l个左括号和r个右括号组成的括号序列的数目。
int n, k;


void init(){
    dp[0][0][0] = 1;

    for (int i=1;i<=K;i++)
        for (int l=1;l<=N;l++)
            for (int r=max(l-i,0);r<=l;r++){
                dp[i][l][r] = dp[i][l-1][r] + dp[i][l][r-1];
                if (l - r == i)
                    dp[i][l][r] += dp[i-1][l-1][r];
            }
}

int main(){
    init(); int T = 0; bool first_blood = true;
    while (scanf("%d%d", &n, &k) == 2 && n != 0){
        if (!first_blood) cout << endl; else first_blood = false;
        cout << "Case " << ++T << ": " << dp[k][n][n] << endl;
    }
}

Posted by xiaodao
Category: 日常