1369. 牛之关系谱

状态表示:

(f(i,j)):节点数为(i),高度不超过(j)的子树个数(定义成高度恰好为(j)不好计算)。

状态转移:

若左子树的节点数为(k),则右子树的节点数为(i-k-1)

[f(i,j)=sum_{k=1}^{i-2} f(k,j-1) imes f(i-k-1,j-1) ]

边界:

叶节点的节点数为(1),高度不超过(1 sim k)

[f(1,1sim k)=1 ]

const int N=210,M=110;
int f[N][M];
int n,m;

int main()
{
    cin>>n>>m;
    
    for(int i=1;i<=m;i++) f[1][i]=1;
    
    for(int i=2;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=1;k<=i-2;k++)
                f[i][j]=(f[i][j]+f[k][j-1] * f[i-k-1][j-1])%mod;
        
    cout<< (f[n][m]-f[n][m-1]+mod)%mod <<endl;
    //system("pause");
    return 0;
}
原文地址:https://www.cnblogs.com/fxh0707/p/14855635.html