正文
D. How many trees? DP
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
D. How many trees?
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output
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 test(s)
input
3 2
output
5
input
3 3
output
4 题解：（我网上看到的）最后的状态是什么?也就是说求的是什么? N个节点h>=H的二差索引树的种数。能不能简化一下，因为这样直接求每次要判断h >= H ? 很难处理的，而且容易漏。想一想高度大于H的数可不可以通过某些数据相减得到？哦，可以这样表述：Ｎ个节点高度不大于Ｎ的树的种数－Ｎ个节点高度不大于Ｈ－１的种数就是题目所求的。很好！那么有没有什么想法？没有。再想一下最后的结果和那些状态有关? 节点数N和高度h。很好！那么节点数为N高度为h的树的种数是怎么得到的?是通过两棵子树种数的乘积得到的。能不能再具体一些，稍微用一下数学式子表示一下? Dp[k][n] = dp[~-k][i] * dp[~-k][n - i - 1] , 其中k是高度,n是节点数,i是左儿子的节点数，n - i - 1 是右儿子的节点数。非常好，你的思路是完全正确的。那么能不能再考虑一下初始条件是什么?...打个比方说：dp[0][0] = ? dp[0][1] = ? dp[1][0] = ? ... Oh！dp[0][i] = 0 , ( 1 <= i <= n ) dp[i][0] = 1 ( 0 <= i <= n ) , 很好，现在可以写代码了.
#include <iostream>
#include <string.h>
using namespace std;
long long dp[][];
int main()
{
int n,h,i,j,k;
cin>>n>>h;
memset(dp,,sizeof(dp));
for(i=; i<=n; i++)
dp[i][]=;
for(i=; i<=n; i++)
{
for(j=; j<=n; j++)
{
for(k=; k<j; k++)
{
dp[i][j]+=dp[i-][k]*dp[i-][j-k-];
}cout<<dp[i][j]<<" ";
}cout<<endl;
}
cout<<dp[n][n]-dp[h-][n]<<endl;
}
