最优二叉检索树¶

背景故事¶

检索系统保存一组按编号排序的条目。频繁访问的条目适合放在较浅的位置，但整棵树仍须满足二叉搜索树的顺序。请选择总代价最小的布局。

(本故事由GPT-6重写)

把编号 \(1,\ldots,n\) 各使用一次，组成一棵二叉搜索树：每个结点左子树的编号都小于它，右子树的编号都大于它。根的深度为一，孩子的深度等于父亲深度加一。

编号 \(i\) 的访问次数为 \(f_i\) ，总代价为 \(\sum_{i=1}^n f_i d_i\) ，其中 \(d_i\) 是它的深度。求最小总代价，并输出所有最优树中字典序最小的先序遍历。

先序遍历依次访问根、左子树和右子树。字典序按整数比较，第一个不同位置的编号较小者更小；不是按编号的十进制字符串比较。访问次数已包含整次检索的需求，不额外累加祖先的访问次数。

第一行一个整数 \(n\) .第二行 \(n\) 个整数 \(f_1,\ldots,f_n\) .

第一行输出最小总代价。第二行输出最优树中字典序最小的先序遍历，相邻编号以空格分隔。

3
2 10 2

18
2 1 3

以二号结点为根，总代价为 \(10+2\cdot2+2\cdot2=18\) .

圆圈标明结点编号，旁边列出频次和深度。

4
0 0 0 0

0
1 2 3 4

所有树的代价都是零；从一号结点开始的全右链给出最小先序序列。

1
1000000000

1000000000
1

唯一结点的深度为一。

\(1\le n\le500\) ；\(0\le f_i\le10^9\) .所有输入均为整数；零次访问的条目也必须出现在树中。

数据规格由 Codex（GPT-6）补齐：确定上述规模、非负访问次数和零权值边界，并提供对应测试分组。