P1267 排序二叉树 题解

fervency · 2022-09-22 19:41:50 · 题解

我会说我在水咕值吗

由于本人是蒟蒻，有错误请指正！qwq

题意还是很清晰的，其中排序二叉树是指对于每一个有儿子的节点，其左儿子一定小于这个节点，其右儿子一定大于这个节点，我们按照题目要求建图即可（代码中有相应注释）。

但是！！！ 对于样例，有两种选择：

• 直接复制粘贴，正确代码输出应该为 9；
• 这里提供正确输入格式的样例，其正确答案确实为 17；

  3 
  19
  33 32 31
  29 3 5 4 30
  22
  25 20 21
  12 24 23 34 35
  14
  13 15 26
  18 17 8 16 27
  11
  10 9 1
  28 7 2 6 36

读完题来继续处理，对于一个随机二叉树，有什么办法去枚举节点呢？注意到排序二叉树的性质：

1. 对于一节点，其儿子的子树也是排序二叉树。

2. 对于一节点，其左右子树不交叉，满足枚举时无后效性（即左子树对右子树无影响）。

同时，若要使树最大，那么左右子树都要是最大的，局部最优满足全局最优，这就是妥妥的 DP 了（在图中还是记忆化更简单一些）。

知道是 DP 后我们来找状态，考虑到 n 的范围在 [1,18]，4n^2 也不会超空间，所以可以用桶的思想，结合排序二叉树性质：

若一个点范围是 l 到 r，此时枚举到 num 节点：

那么其左儿子范围是 l 到 num-1，右儿子范围是 num+1 到 r。已经确定父亲节点的时候，只要枚举周围 3 个相邻单位三角形就可以确定了，所以空间复杂度是 n^2 级别的。

在搜索的时候，我们要传下去：