NowCoder 202F – 平衡二叉树 (贪心+递归)

题意

平衡二叉树的参数$d$表示每个节点两子树高度差不超过$d$。求高度为$n$的所有平衡二叉树中左右子树节点数差的最大值。

思路

一开始以为只要左边全满右边一条链就搞定了然后快乐WA

思考后发现右边的所有节点也要满足高度差$\le d$的条件。所以只要左边是满二叉树右边是满足平衡条件的最小二叉树就可以了。

最小二叉树节点数可用递归求出,$$C_h = C_{h-1} + 1 + C_{h-1-d}$$

然后TLE了(内心OS:出题人一定是清华的,又红又橙的题,还是树)

用记忆化搜索还因为垃圾代码越界WA找了半天……

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mt[100] = {};
ll mintree(int h, int d) {
  if (h <= 0) return 0;
  if (mt[h] >= 0) return mt[h];
  else if (h == 1) return 1;
  else return mt[h] = mintree(h - 1, d) + mintree(h - 1 - d, d) + 1;
}

int main() {
  memset(mt, -1, sizeof(mt));
  int n = 0, d = 0;
  ll ans = 0;
  scanf("%d%d", &n, &d);
  if (n == 0) {
    ans = 0;
  } else {
    ans = (1LL << (n - 1)) - 1 - mintree(n - 1 - d, d);
  }
  printf("%lld", ans);
}