题解：P12223 [蓝桥杯 2023 国 Java B] 非对称二叉树

Cipher0128 · 2025-05-06 22:10:00 · 题解

这题还没有题解……

很容易发现是计数动态规划，考虑状态。

至少有一维是节点数，但为了满足高度限制，需多加一维，表示高度，所以有了状态 f_{i,j} 表示 i 个点高度为 j 的方案数。

枚举子树根节点状态与其左右子状态，进行转移。

初始化 f_{0,0}=1。

答案即为 \sum_{h=1}^nf_{n,h}。

#include<bits/stdc++.h>
#define ll long long
#define for_(a,b,c) for(int a=b;a<=c;++a)
#define For_(a,b,c) for(int a=b;a>=c;--a)
using namespace std;
int n,k;
const int N=40;
ll f[N][N];
int main(){
    cin>>n>>k;
    f[0][0]=1;
    for_(cnt,0,n){
        for_(cntl,0,n){
        int cntr=cnt-1-cntl;
        if(cntr<0)continue;
            for_(hl,0,cntl){
                for_(hr,0,cntr){
                    int h=max(hl,hr)+1;
                    if(h>cnt)continue;
                    if(max(hl,hr)>=k*min(hl,hr)){
                        f[cnt][h]+=f[cntl][hl]*f[cntr][hr];
                    }
                }
            }
        }
    }

    ll ans=0;
    for_(i,0,n)ans+=f[n][i];
    cout<<ans;

    return 0;
}