太空紧急状态 - 题目

太空发生紧急情况！你需要让你的旗舰以最快速度从 0 号星航行到 $N$ 号星，途中必须按编号递增的顺序经过其他所有星系（$0 \to 1 \to \dots \to N$）。你的旗舰正常航行速度为每小时 0.5 秒差距。

除了派遣旗舰外，你还可以命令工程师在不同的星系建造最多 $L$ 个加速器。建造一个加速器需要 $t$ 小时，所有 $L$ 个加速器可以并行建造。当旗舰从一个已建成加速器的星系出发前往下一个星系时，其航行速度为每小时 1 秒差距。

如果旗舰在从某个星系前往下一个星系的途中，该星系的加速器建造完成，那么旗舰会在加速器建成后立即加速。

如果你通过建造加速器使旗舰尽可能快地到达 $N$ 号星，请问旗舰到达 $N$ 号星需要多少小时？

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 行，每行包含整数 $L, t, N, C$，随后是 $C$ 个整数 $a_i$，所有数字均以空格分隔。对于所有整数 $k$，距离星系 $k \cdot C + i$ 与星系 $k \cdot C + i + 1$ 之间的距离为 $a_i$。

例如，当 $N=8, C=3, a_0=3, a_1=5, a_2=4$ 时，星系间的距离序列为 $[3, 5, 4, 3, 5, 4, 3, 5]$。

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是用例编号（从 1 开始），$y$ 是一个整数：到达 $N$ 号星所需的小时数。题目保证答案始终为整数。

$1 \le T \le 100$。 $1 \le C \le 1000$。 $C \le N$。 $1 \le a_i \le 10^4$。 $0 \le t \le 10^{11}$。 $t$ 为偶数。

$1 \le N \le 1000$。 $0 \le L \le 2$。

$1 \le N \le 10^6$。 $0 \le L \le N$。

2
2 20 8 2 3 5
1 4 2 2 10 4

Case #1: 54
Case #2: 20

在第二个样例中，我们可以建造一个加速器。星系间的距离为 $[10, 4]$。我们在第一个星系建造加速器。4 小时后，旗舰航行了 2 秒差距，此时加速器建成。旗舰再花 8 小时到达 1 号星，随后再花 8 小时到达目的地 2 号星。

注意： 本题所处的宇宙中光速远高于每小时 1 秒差距，因此无需考虑狭义相对论效应。

QOJ.ac