这个题坑点在于和我们一般的BBT不一样。我们说平衡因子一般是要<d。但是这里是<=d。这点要注意。

然后就来分析一下题目。

  • 首先,特判两种情况n=1||n==0输出0就行了

  • 考虑一般情况,画个图发现,如果f[n]表示平衡因子不超过d的最小结点数量。那么f[n]=1+f[n-1]+f[n-1-d].前提是n>=d+1
    那么n<d+1呢?很简单,一条链就ok

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll f[70];
    int main()
    {
    ll n,d;
    cin>>n>>d;
    f[0]=0;
    if(n==0||n==1) return cout<<0<<endl,0;
    for(int i=1;i<=d+1;i++ ) f[i]=i;//一条链就是满足条件的最少数量形态
    for(int i=d+2;i<=n;i++) f[i]=f[i-1]+f[i-1-d]+1;//考虑合并左右子树
    
    cout<<(1ll<<(n-1))-1-f[n-1-d]<<endl;
    return 0;
    }