51nod 1412 AVL树的种类( dp )

题目链接

题目大意

平衡二叉树(AVL树），是指左右子树高度差至多为1的二叉树，并且该树的左右两个子树也均为AVL树。 现在问题来了，给定AVL树的节点个数n，求有多少种形态的AVL树恰好有n个节点。(n<=2000)

解答

一开始想先构个接近n的满二叉树，用组合数搞搞，然后发现naive了。后来还是老老实实的用dp来解决。
由于AVL的层数很小，是1.5*log(n)级别的，所以我们可以用dp[dep][i]表示深度为dep结点数为i的方案数。然后我们每次固定树的根，枚举左右儿子个数进行转移。
转移方程如下：
dp[dep][ i ]=∑ (dp[dep-1][ j ] × dp[dep-1][ i-j-1 ] + dp[dep-1][ j ] × dep[dep-2][ i-j-1 ] + dp[dep-2][ j ] × dep[dep-1][ i-j-1 ] )( 0<=j<i )
时间复杂度是O(n^2 × log(n))

由于AVL树的最高高度有一个至少结点数的递推公式，minf[0]=0，minf[1]=1，minf[i]=minf[i-1]+minf[i-2]+1(i>=2)。所以每个深度的结点数有上下界（上届是满二叉树的时候），用这个性质可以做一个小小的优化，避免无用的枚举。

如果这题的n扩大到10000，甚至更多，我们观察递推公式，由dep-1和dep-2推出dep，可以发现左右子树结点个数的和是i-1，满足fft的式子。因此我们可以用fft优化做到O(n × (log(n))^2)的复杂度。

倘若把这题的二叉树条件换成四叉树，其他都不变，可以变成一道很有意思的题目，dp的时候要注意技巧。这个问题和codeforces 300D基本一样，不过cf这题的题目背景和内容更加有趣。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;

#define bll long long
#define For(i,a,b) for (int i=(a),_##i=(b); i<=_##i; i++)
#define Rof(i,a,b) for (int i=(a),_##i=(b); i>=_##i; i--)

const int maxn=2048+10;
const int modd=1000000007;
int N;
int minf[25],maxf[25];
int dp[25][maxn];

int Done()
{
    minf[0]=maxf[0]=0;
    minf[1]=maxf[1]=1;
    For(i,2,20)
    {
        minf[i]=minf[i-1]+minf[i-2]+1;
        maxf[i]=(1<<i)-1;
    }
    memset(dp,0,sizeof dp);
    dp[0][0]=1;
    dp[1][1]=1;
    For(i,2,N)
    {
        For(dep,2,20)
            if (minf[dep]<=i && i<=maxf[dep])
            {
                int ret=0;
                For(j,minf[dep-1],min(maxf[dep-1],i-1))
                {
                    int k=i-1-j;
                    ret=(ret+(bll)dp[dep-1][j]*dp[dep-1][k]) %modd;
                    ret=(ret+(bll)dp[dep-1][j]*dp[dep-2][k]) %modd;
                }
                For(j,minf[dep-2],min(maxf[dep-2],i-1))
                {
                    int k=i-1-j;
                    ret=(ret+(bll)dp[dep-2][j]*dp[dep-1][k]) %modd;
                }
                dp[dep][i]=ret;
            }
    }
    int ans=0;
    For(dep,1,20)
        ans=(ans+dp[dep][N]) %modd;
    return ans;
}

int main(int argc, char* argv[])
{
    for (; scanf("%d",&N)!=EOF; )
    {
        int ans=Done();
        printf("%d\n",ans);
    }
    return 0;
}