国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

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

發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板： 墨脱县| 仁怀市| 玉林市| 灵武市| 张家口市| 利川市| 邢台县| 嵊州市| 涿鹿县| 安化县| 绥芬河市| 竹山县| 清涧县| 理塘县| 凤凰县| 高安市| 霍林郭勒市| 柞水县| 龙里县| 广安市| 昂仁县| 湘潭县| 丰顺县| 郑州市| 宁阳县| 本溪市| 宜宾县| 聂拉木县| 景谷| 河间市| 潜山县| 儋州市| 论坛| 横峰县| 忻城县| 环江| 万年县| 苍山县| 临洮县| 左云县| 宁晋县|