51Nod-1603-限高二叉排列树

3/8/2017来源:ASP.NET技巧人气:2352

ACM模版

描述

描述

题解

题目好长,长得我看了两遍都没有看懂,看来学理工科时间长了,语文水平有所下降。

简单地说,也就是求 n 个结点所能构成的高度大于等于 h 的二叉树种数。典型的 dp 问题,设 dp[i][j] 表示 i 个结点且高度小于等于 j 的树个数,中间利用乘法原理合并树累加求各个状态结果,最后输出 dp[n][n] - dp[n][h - 1] 即可。

代码

#include <iostream> using namespace std; typedef long long ll; const int MAXN = 40; ll dp[MAXN][MAXN]; // dp[i][j] i 个结点且高度小于等于 j 的树个数 int main() { int n, h; scanf("%d%d", &n, &h); for (int i = 0; i <= n; i++) { dp[0][i] = 1; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { for (int k = 1; k <= i; k++) { dp[i][j] += dp[k - 1][j - 1] * dp[i - k][j - 1]; // 乘法原理合并树 } } } cout << dp[n][n] - dp[n][h - 1] << endl; return 0; }