P16660 [GKS 2018 #H] Mural

Thanh 想要在一面长度为 $N$ 段的墙上绘制一幅美妙的壁画。墙的每一段都有一个美丽值，表示该段被绘制后会多么好看。不幸的是，由于最近的一场洪水，墙壁开始被冲毁，所以他必须加快速度！ 每天开始时，Thanh 会绘制墙上的一个段落。第一天，他可以自由选择任意段落进行绘制。在随后的每一天，他必须绘制一个与已绘制段落相邻的新段落，因为他不希望将壁画分割开。 每天结束时，墙上的一个段落会被毁坏。被毁坏的段落总是只与另一个段落相邻且未被绘制的段落（Thanh 使用的是防水涂料，因此已绘制的段落不会被毁坏）。 Thanh 壁画的总美丽值等于他所绘制段落美丽值的总和。Thanh 希望保证，无论墙壁如何被毁坏，他都能获得至少 $B$ 的总美丽值。他能保证的最大 $B$ 值是多少？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$。然后，另一行包含一个由 $0$ 到 $9$ 数字组成的长度为 $N$ 的字符串。第 $i$ 个数字表示墙上第 $i$ 个段落的美丽值。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是 Thanh 能保证获得的最大美丽值，如上所述。

在第一个样例中，无论墙壁如何被毁坏，Thanh 都能获得总美丽值 $6$。第一天，他可以绘制美丽值为 $3$ 的段落（两端的 $3$ 均可）。当天结束时，要么第 $1$ 段要么第 $4$ 段会被毁坏，但具体哪一段并不重要。第二天，他可以绘制另一个美丽值为 $3$ 的段落。 在第二个样例中，Thanh 通过绘制最左边的段落（美丽值 $9$）可以获得总美丽值 $14$。唯一可能被毁坏的段落是最右边的段落，因为最左边的段落已被绘制。第二天，他可以绘制左起第二个段落（美丽值 $5$）。然后右边最后一个未绘制的段落被毁坏。注意，第二天 Thanh 不能选择绘制第三段（美丽值 $8$），因为它与任何已绘制段落都不相邻。 在第三个样例中，Thanh 可以获得总美丽值 $7$。他首先绘制中间段落（美丽值 $1$）。无论当天结束时哪一段被毁坏，他都可以在第二天开始时绘制剩余的段落。 ### 限制条件 $1 \le T \le 100$。 **小数据集（测试集 1 – 可见）** $2 \le N \le 100$。 **大数据集（测试集 2 – 隐藏）** 恰好有一个测试用例满足 $N = 5 \times 10^6$；其余 $T-1$ 个测试用例满足 $2 \le N \le 100$。 翻译由 DeepSeek V4 Pro 完成