【wanaflyCamp】平衡二叉树（dp）

题目描述

平衡二叉树，顾名思义就是一棵“平衡”的二叉树。在这道题中，“平衡”的定义为，对于树中任意一个节点，都满足左右子树的高度差不超过 . 空树的高度定义为0，单个节点的高度为1，其他情况下树的高度定义为根节点左右子树高度最大值 + 1。 一棵在高度上平衡的树，节点数可能不平衡。再定义一棵树的不平衡度为这棵树中所有节点的左右子树的节点数之差的最大值。

给定平衡的定义参数, 你需要求出所有高度为 的平衡树中不平衡度的最大值。

输入

两个整数，.

输出

一个整数：所有高度为 的平衡树中不平衡度的最大值。

样例输入
4 1

样例输出
5

提示

数据范围

0 <= n, d <= 60

样例解释

下面这棵树在 的定义下高度是平衡的，其不平衡度为 5。

我的做法是用dp递推，不过似乎有人打表找到斐波那契的规律，后来发现的确是类似与原根斐波那契的数列。
我们要差值最大，则假设做边是完全二叉树，那么有边的节点就要尽量小
设：$dp[i][j]$为树高为$i$,子树高度差为j时,节点的最小值。
所以答案就是：做子树减去又子树。
转移：

$$dp[i][j]=1+min_{0<=k<=j} \{ dp[i-1][k]+min_{i-1-k<=l<=i-1}\{min_{0<=t<=d}\{dp[l][t]\}\}\}$$

我们可以发现原式性质，就是当i固定时，显然$dp[i][j]$会随着j增大而减小，当i<=j时，值就是为i；当j固定，i变大，值显然递增。

所以上式可以化简。

$$dp[i][j]=1+ dp[i-1][d]+dp[i-1-d][d]$$
那么 $$dp[i][d]=1+ dp[i-1][d]+dp[i-1-d][d]$$
发现可以把第二维去掉，就是 $$dp[i]=1+ dp[i-1]+dp[i-1-d]$$

当i<=d,dp[i]=i,然后就可以递推了，不过朴素dp递推也可以过啦。
代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxx 65
#define ll long long
using namespace std;
ll const INF = 0x7fffffffffffffff;
ll dp[65][65];
int n,d;
ll work(int i,int j)
{
    if(i<=j)return i;
    if(dp[i][j]!=INF) return dp[i][j];
    dp[i][j]=work(i-1,j)+work(i-1-j,d)+1;
    return dp[i][j];
}
ll get(int x)
{
    if(x==1)return 0;
    ll ans=1;
    ll temp=1;
    for(int i=1;i<=x-2;i++)
    {
        temp*=2;
        ans+=temp;
    }
    return ans;
}
main()
{
    while(scanf("%d%d",&n,&d)==2)
    {
        if(n<=1) 
        {
            cout<<0<<endl;
            continue;
        }
        for(int i=0;i<=n;i++)
        for(int j=0;j<=d;j++)dp[i][j]=INF;

        for(int i=0;i<=d;i++) dp[0][i]=0;
        for(int i=0;i<=d;i++) dp[1][i]=1;
        if(n-1<=d)
            cout<<get(n)<<endl;
        else
        cout<<get(n)-work(n-1-d,d)<<endl; 
    }
    return 0;
} 
/**************************************************************
    Problem: 1087
    User: coldfresh
    Language: C++
    Result: 正确
    Time:0 ms
    Memory:1568 kb
****************************************************************/