自动搬运

查看原文

来自洛谷，原作者为

	Cipher0128 ALL IN.

搬运于2025-08-24 23:13:49，当前版本为作者最后更新于2025-05-06 22:10:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题还没有题解……

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

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

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

$f_{y,h}=\sum f_{y_1,h_1}\times f_{y_2,h_2}$

初始化 $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;
}