Phonebook shelf tree

Arrange the names in a phone directory app as a binary search tree that needs the fewest comparisons.

The app stores n distinct names in sorted order, numbered 0 to n - 1, in a binary search tree: every name in a node's left subtree sorts before it, every name in its right subtree sorts after it. You choose the shape of the tree.

Every day people look up names. hits[i] is how many times name i is searched for and found. misses[j] is how many searches are for a name that is not stored and that sorts after name j - 1 and before name j (misses[0] is before name 0, misses[n] is after the last name).

A search starts at the root and compares the searched name with the node it is at, one comparison per node visited, going left or right until it finds the name or falls off the tree. A hit on a node at depth d (the root has depth 1) costs d comparisons. A miss costs the number of nodes it visited before falling off the tree, which is the depth of the last node on its path. With no names at all, a search visits no nodes and costs 0.

Input: hits, the daily hit count for each name, and misses, the daily counts of misses by gap.

Output: the smallest possible total number of comparisons per day over all valid trees.

There are far too many tree shapes to try each one, even for 40 names.