#9 (Div. 2 Only) D. How many trees? （dp）（好题）

Dear 丶 2022-06-17 13:38 145阅读 0赞

题目链接：

[点击打开链接][Link 1]

http://codeforces.com/contest/9/problem/D

题意：

规定一个二叉树，有n个节点，问你深度大于等于h的一共有多少种？这个二叉树满足左儿子比自己小，右儿子比自己大的特性。

题解：

dp。

假设dp\[ i \]\[ j \]表示当前用了 i 个节点，深度度小于等于 j 的方案数。

如果我们直接求深度大于等于h有点难。那么我们就求深度小于等于h的。那么，n个节点高度小于等于n的树的种数，减去，n个节点高度小于等于h-1的种数，这就是我们要求的方案数。

假设节点数n和高度h。那么节点数为n，高度为h的树的种数是怎么得到的?答案是通过两棵子树（高度减一）的种数的乘积得到的。

那么，我们容易得到转移方程：

dp\[ n \]\[ k \] += dp\[ i \] \[ k - 1\] \* dp\[  n - i - 1 \]\[ k-1 \] , 其中k是高度,n是节点数,i是左儿子的节点数，n - i - 1 是右儿子的节点数。

显然要枚举高度 k，节点数n，还有左儿子节点数或者右儿子节点数。

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll dp[40][40];
    //n个节点高度小于等于n的树的种数－n个节点高度小于等于h-1的种数
    int main()
    {
    	int n,h;
    	cin>>n>>h;
    	for(int i=1;i<=n;i++)//高度 
    	{  
    		dp[0][i-1] = 1;
    		for(int j=1;j<=n;j++)//拿n个节点
    		{
    			for(int k=0;k<j;k++)//左子树 
    			{
    				dp[j][i] += dp[k][i-1] * dp[j-k-1][i-1];
    			}
    		}		
    	}
    	cout<<dp[n][n]-dp[n][h-1]<<endl;
    	return 0;
    }

[Link 1]: http://codeforces.com/contest/9/problem/D

发表评论取消回复

表情：

评论列表（有 0 条评论，145人围观）

还没有评论，来说两句吧...

相关阅读

相关 CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!) D. Climbing the Tree

[Problems - Codeforces][] 题意： ![99e173500b7946a4b9dc13783292652e.png][] 思路： ![6a492e

深藏阁楼爱情的钟/ 2024年03月24日 12:59/ 0 赞/ 61 阅读

相关【*1900 DP+Tree】CF9D

[Problem - 9D - Codeforces][] 题意： ![08c35e73a5d74fb1a152f832fd807c81.png][] 思路：计数问

落日映苍穹つ/ 2024年03月16日 10:29/ 0 赞/ 58 阅读

相关 Codeforces Round #329 (Div. 2) D. Happy Tree Party

对于从a→b 的路径，如果边权值为1，则值不变，否则就是1≤边权值，这样的话最多除64次就为0也就不需要继续除下去了，所以问题的关键在于去压缩哪些连续的边权为1的路径，这里自然

Myth丶恋晨/ 2022年08月10日 00:53/ 0 赞/ 31 阅读

相关 uva 10061——How many zero\'s and how many digits ?

题意：这道题开始是卡了很久的，题意是给定一个数n然后让你求B进制下n！有多少个零，和有多少位数，咋一看，是高精度，如果数论不是很熟系。思路：开始是直接抛弃高精度的一

傷城~/ 2022年08月09日 13:49/ 0 赞/ 38 阅读

相关 #9 (Div. 2 Only) D. How many trees? （dp）（好题）

题目链接： [点击打开链接][Link 1] http://codeforces.com/contest/9/problem/D 题意：规定一个二叉树，有

Dear 丶/ 2022年06月17日 13:38/ 0 赞/ 146 阅读

相关 #9 (Div. 2 Only) B. Running Student （枚举）

题目链接： [点击打开链接][Link 1] http://codeforces.com/contest/9/problem/B 题意：给你车的速度，人跑步的

古城微笑少年丶/ 2022年06月17日 13:37/ 0 赞/ 88 阅读

相关 How Many Tables

Problem Description：今天是伊格内修斯的生日。他邀请了很多朋友。现在是晚餐时间。伊格内修斯想知道他至少需要多少张桌子。你必须注意，并非所有的朋友都彼此认识

向右看齐/ 2022年05月28日 02:11/ 0 赞/ 151 阅读

相关 uva 10303 - How Many Trees?(卡特兰数）

[题目链接：uva 10303 - How Many Trees?][uva 10303 - How Many Trees] 卡特兰数，公式num\[i + 1\]

迈不过友情╰/ 2022年05月14日 13:52/ 0 赞/ 151 阅读

相关 F - How Many Tables

题目描述： Today is Ignatius’ birthday. He invites a lot of friends. Now it’s dinner time.

比眉伴天荒/ 2022年03月19日 11:28/ 0 赞/ 182 阅读

相关 How Many Tables HDOJ

[How Many Tables][] Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/327

清疚/ 2021年12月20日 23:39/ 0 赞/ 232 阅读