博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Codeforces Beta Round #9 (Div. 2 Only) D. How many trees? dp
阅读量:6407 次
发布时间:2019-06-23

本文共 2620 字,大约阅读时间需要 8 分钟。

D. How many trees?

题目连接:

Description

In one very old text file there was written Great Wisdom. This Wisdom was so Great that nobody could decipher it, even Phong — the oldest among the inhabitants of Mainframe. But still he managed to get some information from there. For example, he managed to learn that User launches games for pleasure — and then terrible Game Cubes fall down on the city, bringing death to those modules, who cannot win the game...

For sure, as guard Bob appeared in Mainframe many modules stopped fearing Game Cubes. Because Bob (as he is alive yet) has never been defeated by User, and he always meddles with Game Cubes, because he is programmed to this.

However, unpleasant situations can happen, when a Game Cube falls down on Lost Angles. Because there lives a nasty virus — Hexadecimal, who is... mmm... very strange. And she likes to play very much. So, willy-nilly, Bob has to play with her first, and then with User.

This time Hexadecimal invented the following entertainment: Bob has to leap over binary search trees with n nodes. We should remind you that a binary search tree is a binary tree, each node has a distinct key, for each node the following is true: the left sub-tree of a node contains only nodes with keys less than the node's key, the right sub-tree of a node contains only nodes with keys greater than the node's key. All the keys are different positive integer numbers from 1 to n. Each node of such a tree can have up to two children, or have no children at all (in the case when a node is a leaf).

In Hexadecimal's game all the trees are different, but the height of each is not lower than h. In this problem «height» stands for the maximum amount of nodes on the way from the root to the remotest leaf, the root node and the leaf itself included. When Bob leaps over a tree, it disappears. Bob gets the access to a Cube, when there are no trees left. He knows how many trees he will have to leap over in the worst case. And you?

Input

The input data contains two space-separated positive integer numbers n and h (n ≤ 35, h ≤ n).

Output

Output one number — the answer to the problem. It is guaranteed that it does not exceed 9·1018.

Sample Input

3 2

Sample Output

5

Hint

题意

问你一个二叉树,有n个节点,深度大于等于h的一共有多少种

这个二叉树满足左儿子比自己小,右儿子比自己大的特性。

题解:

dp,dp[i][j]表示当前用了i个节点,高度小于等于j的方案数

dp[i][j] = sigma(dp[k][j-1]*dp[i-k-1][j-1])

枚举左子树和右子树

然后莽一波就好了

代码

#include
using namespace std;const int maxn = 37;long long dp[maxn][maxn];int main(){ int n,h; scanf("%d%d",&n,&h); for(int i=1;i<=n;i++) { dp[0][i-1]=1; for(int j=1;j<=n;j++) for(int k=0;k

转载地址:http://qmjea.baihongyu.com/

你可能感兴趣的文章
CISCO 路由器(4)
查看>>
网络服务搭建、配置与管理大全(Linux版)
查看>>
Silverlight 5 Beta新特性[4]文本缩进控制
查看>>
springMVC多数据源使用 跨库跨连接
查看>>
Git服务端和客户端安装笔记
查看>>
Spring Security(14)——权限鉴定基础
查看>>
IntelliJ IDEA快捷键
查看>>
【iOS-cocos2d-X 游戏开发之十三】cocos2dx通过Jni调用Android的Java层代码(下)
查看>>
MongoDB的基础使用
查看>>
进程间通信——命名管道
查看>>
ssh登陆不需要密码
查看>>
java mkdir()和mkdirs()区别
查看>>
windows server 2003各版本及2008各版本的最大识别内存大小
查看>>
OSChina 周六乱弹 ——揭秘后羿怎么死的
查看>>
IT人员的职业生涯规划
查看>>
sorry,you must have a tty to run sudo
查看>>
ios开发中使用正则表达式识别处理字符串中的URL
查看>>
项目中的积累,及常见小问题
查看>>
Python类型转换、数值操作(收藏)
查看>>
oracle11g dataguard 安装手册(转)
查看>>