C1644 [Wannafly冬令营2018Day2]Erase Numbers II

内存限制:256 MB 时间限制:1000 ms

题目描述

给定 $n$ 个正整数 $a_1, a_2, \cdots, a_n$,它们组成了序列 $A$。

你的任务是删除其中 $(n - 2)$ 数字,使得 $A$ 中剩余的数字连起来的所表示的数字最大,并给出这个值。

严格来讲,如果剩余数字在 $A$ 中的下标为 $p_1, p_2, \cdots, p_m$ ($1 \leq p_1 < p_2 < \cdots < p_m \leq n$),则它们连起来所表示的数字为 $\overline{a_{p_1} a_{p_2} \cdots a_{p_m}}$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$,表示测试数据的组数。随后的内容是各组测试数据。对于每组测试数据:

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$,保证每个数字不含前导零。

  • $1 \leq T \leq 3000$
  • $2 \leq n \leq 6000$
  • $1 \leq a_i \leq 10^9$
  • 所有测试数据的 $n$ 之和不超过 $6000$。

输出

对于每组测试数据,输出一行Case #x: y(不含引号),其中x是测试数据的编号(从 $1$ 开始编号),y是这组数据的答案。

样例

样例输入 1

3 3 6 6 6 4 21 12 12 21 2 998244353 985661441

样例输出 1

Case #1: 66 Case #2: 2121 Case #3: 998244353985661441

提示