平衡二叉树

题意

给定和，要求一个二叉树，使得任意节点左右子树深度之差不超过，求左右子树节点差值的最大值。

分析

我们可以使左子树节点个数最多，右子树节点个数最少。

左子树显然是一颗满二叉树。

考虑如何求右子树：首先深度尽量小，为。

我们定义表示深度为的子树最少总节点个数。

则转移方程，

可以理解为左边放了一颗深度的子树，右边就得放深度的子树。

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pii pair<int,int>
#define int long long
const int inf = 0x3f3f3f3f;
const int maxn = 70;
const int M = 1e9+7;
int n,d;

int dp[maxn];

signed main()
{
    cin>>n>>d;
    int m = max(n-d-1,0ll);
    dp[1] = 1;
    for(int i = 2; i <= m; i++) 
    {
        dp[i] = dp[i-1]+1;
        if(i >= d+1) dp[i] += dp[i-1-d];
    }
    int ans = (1ll<<(n-1))-1-dp[m];
    cout<<ans<<endl;
    return 0;
}