51nod 1603 限高二叉排列树/1412 AVL树的种类

作为游戏魔方的编写者和管理员，Bob在很多主存模块中检测游戏魔方，并且Bob从未被用户打败，同时他也经常和游戏魔方作战。

然而，不愉快的事情发生了，游戏《失落的洛杉矶》崩溃了，由于出现了一个非常可恶的病毒——“十六进制”，它非常奇怪，并且非常喜欢玩，因此，Bob必须先和它玩，才能和别人玩。

此次“十六进制”发明了以下游戏：Bob必须通过一些有n个节点的二叉搜索树，二叉搜索树是一颗二叉树，每个节点有一个唯一的关键字。我们来说一下二叉搜索树的性质，以下规则在每个节点上都成立：每个节点的关键字都大于左子树上的所有节点的关键字，都小于右子树上所有节点的关键字。每个关键字都是从1~n的不同的正整数。每棵树上的所有节点都最多有两个子节点，或者没有子节点（在这种情况下的节点被称为叶子节点）。

在“十六进制”的游戏中，所有的树都是不同的，但是每棵树的高度都不低于h。在此问题中，“高度”指的是从根节点到最远的叶子节点的最多节点数（包含叶子节点和根节点）。当Bob跳过一棵树的后，这棵树会消失。当所有的树都消失了，Bob就通过了游戏魔方。他想知道在最坏的情况下，他必须跳过多少棵树，你能帮助他吗？
输入
单组测试数据
输入数据包含两个以空格隔开的正整数n和h (1<=n<=35,1<=h<= n) 。
输出
输出一个整数表示问题的答案。题目保证这个整数不超过9*10^18。
输入样例
3 2
输出样例
5

#include<bits/stdc++.h>
#define re register int
#define LL long long
#define maxn 40+5

using namespace std;
int n,h;
LL dp[maxn][maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>h;
    for(re i=0;i<=n;i++)
    dp[0][i]=1;
    for(re i=1;i<=n;i++)
    for(re j=1;j<=n;j++)
    for(re 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];
    return 0;
}

View Code

平衡二叉树(AVL树），是指左右子树高度差至多为1的二叉树，并且该树的左右两个子树也均为AVL树。现在问题来了，给定AVL树的节点个数n，求有多少种形态的AVL树恰好有n个节点。
输入
一行，包含一个整数n。 (0 < n <= 2000)
输出
一行表示结果，由于结果巨大，输出它对1000000007取余数的结果。
输入样例
10
输出样例
60

   附上本题代码

#include<bits/stdc++.h>
#define re register int
#define maxn 2000+5
#define maxn1 20// 打表得到s(16)==2583>2000 
#define LL long long
#define mod 1000000007

using namespace std;
LL dp[maxn][maxn1];
LL ans;
int n;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    dp[0][0]=1,dp[1][1]=1;
    for(re i=2;i<=n;i++)
    for(re h=2;h<=16;h++)
    for(re j=0;j<i;j++)
     {
         dp[i][h]=(dp[i][h]+dp[i-j-1][h-1]*dp[j][h-1])%mod;
         dp[i][h]=(dp[i][h]+2*dp[i-j-1][h-2]*dp[j][h-1])%mod;
     }
     for(re i=0;i<=16;i++)
     ans=(ans+dp[n][i])%mod;
     cout<<ans;
     return 0;
}

View Code