平衡二叉树

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

这个没啥解释的,然后注意看黑体标记
题解:
既然要左右差值最大,那么我们可以人为的规定左子树减右子树,如果要差值最大,那么左子树要时高度为n-1的满二叉树,右子树是为了符合题意并满足左子树的最小树
例如d为2的时候
那么对于在右子树在第n层不需要放,在第n-1层也不需要放,因为对与这两层相关的是根节点,但是到n-2层就必须要放1个(方便理解放在根节点右子树的右子树),如果再不放的话d=3>2不满足题意
那么此时的第对于根节点来说已经满足,下来就算对于根节点右子树的根节点,那么第n-3层也要放1个要不然怎么到n-2层,
n-4层同理
对于第n-5层,就需要在其节点的左子树上放一个,相当于要在n-4层再放一个,否则的话d=3>2
对于第n-6层,就需要在其节点的左子树上放两层,才能满足要求,而如果放两层要最小,也就是如n-2层和n-3
层放两层

如图上得到

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[65];

int main()
{
    int n, d;
    scanf("%d%d", &n, &d);
    for(int i=1; i<=n; i++)
        dp[i] = dp[i-1] + dp[max(i-d-1,0)] + 1;
    printf("%lld", (1ll<<n-1) - 1 - dp[max(n-d-1,0)]);
    return 0;
}