P9893 [ICPC 2018 Qingdao R] Soldier Game

DreamGrid 和 BaoBao 正在玩一个游戏。游戏中有 $n$ 名士兵，编号从 $1$ 到 $n$。第 $i$ 个士兵的战斗力为 $a_i$。DreamGrid 和 BaoBao 将根据以下规则把士兵分成若干个队伍： - 一个队伍必须由 1 或 2 名士兵组成。 - 每个士兵必须属于且仅属于一个队伍。 - 如果一个队伍由两名士兵组成（假设他们是第 $i$ 个和第 $j$ 个士兵），则必须满足 $|i - j| = 1$。 一个队伍的战斗力定义为队伍成员的战斗力之和。为了公平起见，他们希望在分组后最大队伍战斗力与最小队伍战斗力之间的差值最小化。你需要找出这个最小的差值。

无

无

我们现在解释第一个样例测试用例。所有可能的分组如下所示。 | 分组 | 差值 | 分组 | 差值 | | :-: | :-: | :-: | :-:| |[-1], [4], [2], [1], [1] | 4 - (-1) = 5| [-1, 4], [2], [1], [1] | 3 - 1 = 2 | | [-1], [4], [2], [1, 1] | 4 - (-1) = 5 | [-1], [4, 2], [1, 1] | 6 - (-1) = 7 | | [-1], [4], [2, 1], [1] | 4 - (-1) = 5 | [-1, 4], [2], [1, 1] | 3 - 2 = 1 | | [-1], [4, 2], [1], [1] | 6 - (-1) = 7 | [-1, 4], [2, 1], [1] | 3 - 1 = 2 | 所以答案是 $\min(5, 5, 5, 7, 2, 7, 1, 2) = 1$。 题面翻译由 ChatGPT-4o 提供。