来源：牛客网：
@[toc]

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 1048576K，其他语言2097152K
64bit IO Format: %lld

题目描述

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

输入描述:

两个整数，n, d.

输出描述:

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

示例1
输入

4 1

输出

5

说明

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

在这里插入图片描述

备注:

0 ≤ n, d ≤ 60

题解：

不平衡度为这棵树中所有节点的左右子树的节点数之差的最大值
那我们要让不平衡度最大就要尽可能使左右子树差最大，左子树尽可能多，右子树尽可能少
左子树尽可能多的话我们可以直接给拉满，也就是满二叉树节点就是pow(2,n-1),n为整个树的高度，n-1为左子树的高度
右子树尽可能少，那深度就尽可能浅，但因为有题目左右子树的高度差不超过 d的限制，所以右子树的深度就是m=n-1-d。然后右子树也是有左右子子树，同样的道理
我们定义dp[i]表示深度为i的子树最少总节点个数
当前的树高是i，满足题意就是建一颗高度为i-1的左子树和一颗h-d-1的右子树
能得到转移方程：dp[i]=dp[i-1]+dp[i-d-1]+1
这个+1就是+根
我们要求最大的不平衡度
最后用满左子树 -（高度为n-d-1的右子树）- 1

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e3+4;
ll dp[maxn];
int main()
{
    int n,d;
    cin>>n>>d;
    ll sum=0;
    if(n==0||n==1)return cout<<"0", 0;
    sum=(1ll<<(n-1)); 
    dp[1]=1;
    for(int i=2;i<=n-d-1;i++){
        dp[i]=dp[i-1]+1;
        if(i-d-1>=0)dp[i]+=dp[i-d-1];
    }
    cout<<sum-dp[n-d-1]-1<<endl;
    return 0;
}