首页 > 学院 > 开发设计 > 正文

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

2019-11-06 06:01:54

字体：大中小

来源：转载

供稿：网友

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; }

上一篇：easyui在选项卡中打开树形菜单

下一篇：Executor框架

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注

新闻热点

荣耀总裁赵明乌镇演讲：荣耀首款5G手机V30下月发布

2019-10-23 09:17:05

搜狐张朝阳：回归媒体是搜狐重新崛起的关键

2019-10-21 09:20:02

华为轮值董事长郭平：虚拟技术创造现实价值

2019-10-21 09:00:12

滴滴英文服务上线两周年用户已超200万

2019-09-26 08:57:12

华为推出全球至快AI训练集群Atlas900

2019-09-25 08:46:36

马斯克：特斯拉正组建中国技术团队

2019-09-25 08:15:43

疑难解答

图片精选

网友关注