P13439 [GCJ 2009 #1C] Bribe the Prisoners

在一个王国里，有一些牢房（编号为 $1$ 到 $P$），这些牢房排成一条直线。编号为 $i$ 和 $i+1$ 的牢房是相邻的，相邻牢房中的囚犯被称为“邻居”。相邻牢房之间有一堵带窗户的墙，邻居们可以通过窗户进行交流。 所有囚犯本来相安无事，直到有囚犯被释放。当某个囚犯被释放时，他的邻居会得知这个消息，并且每个邻居会把这个消息传递给他的另一个邻居。如此传递下去，直到消息传到没有其他邻居的囚犯（即处在第 $1$ 号牢房、第 $P$ 号牢房，或其相邻牢房已空的囚犯）。每当某个囚犯得知有其他囚犯被释放时，除非他被贿赂一枚金币，否则他会愤怒地砸坏自己牢房里的所有东西。因此，当释放编号为 $A$ 的囚犯时，$A$ 号牢房两侧的所有囚犯——从 $A$ 向左直到第 $1$ 号牢房、向右直到第 $P$ 号牢房或遇到空牢房为止——都需要被贿赂。 假设每个牢房最初都正好关押着一名囚犯，并且每天只能释放一个囚犯。给定 $Q$ 个将要被释放的囚犯（共需 $Q$ 天），请你计算，如果可以任意选择释放顺序，最少需要多少金币用于贿赂。 注意，每一次贿赂只对当天有效。如果某个囚犯昨天被贿赂了，今天又听说有囚犯被释放，他还需要再次被贿赂。

输入的第一行是测试用例数 $N$。接下来有 $N$ 组测试数据。每组数据包含两行。第一行为： $P \ Q$ 其中 $P$ 是牢房的总数，$Q$ 是需要释放的囚犯数。 接下来一行包含 $Q$ 个不同的牢房编号（要被释放的囚犯所在牢房），用空格分隔，按升序排列。

对于每组测试数据，输出一行，格式如下： Case #$X$: $C$ 其中 $X$ 是测试编号（从 $1$ 开始），$C$ 是最少需要的金币数。

**样例说明** 在第二个样例中，假如你先释放 14 号牢房的囚犯，再释放 6 号，最后释放 3 号，所需金币数为 $19 + 12 + 4 = 35$。如果你先释放 6 号，再释放 3 号，最后释放 14 号，所需金币数为 $19 + 4 + 13 = 36$。 **限制条件** - $1 \leq N \leq 100$ - $Q \leq P$ - 每个牢房编号均为 $1$ 到 $P$ 之间的整数 **小数据集** - 时间限制：2 秒 - $1 \leq P \leq 100$ - $1 \leq Q \leq 5$ **大数据集** - 时间限制：3 秒 - $1 \leq P \leq 10000$ - $1 \leq Q \leq 100$ 翻译由 ChatGPT-4.1 完成。