P13233 [GCJ 2015 Finals] Costly Binary Search

你被要求实现可以说是最重要的算法之一：二分查找。更准确地说，你有一个已排序的对象数组，以及一个你想要插入到数组中的新对象。为了找到插入的位置，你可以将你的对象与数组中的对象进行比较。每次比较的结果要么是“更大”，意味着你的对象应该插入到被比较对象的右侧；要么是“更小”，意味着你的对象应该插入到被比较对象的左侧。为简化问题，比较结果不会出现“相等”。保证当你的对象大于数组中的某个对象时，也大于该对象左侧的所有对象；同理，当你的对象小于数组中的某个对象时，也小于该对象右侧的所有对象。如果数组有 $n$ 个元素，那么你的算法可能有 $n+1$ 种不同的结果。 在本题中，并非所有的比较花费都是相同的。更准确地说，将你的对象与数组中第 $i$ 个对象进行比较的代价为 $a_i$，其中 $a_i$ 是一个介于 1 到 9 之间的整数。 你的二分查找在最坏情况下的总代价是多少？假设你总是采用最优策略，尽量使最坏情况下的总代价最小。

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 行，每行包含一个数字序列，描述一个测试用例的比较代价 $a_i$。数组的大小 $n$ 由该序列的长度给出。

对于每个测试用例，输出一行，格式为 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是最坏情况下二分查找的总代价。

**样例说明** - $1 \leq T \leq 50$。 - 所有数字都在 1 到 9 之间。 - 每行数字之间没有空格。 **小数据集（8 分）** - 时间限制：5 秒。 - $1 \leq n \leq 10^{4}$。 **大数据集（19 分）** - 时间限制：30 秒。 - $1 \leq n \leq 10^{6}$。 由 ChatGPT 4.1 翻译