题解

思路

首都只需向右迁移，且若最终停在 $x_i$，到达它之前可依次征服并迁都，总花费为 $(a+b)x_i$。之后所有右侧王国都从 $x_i$ 征服。

于是可以枚举最终有意义的首都位置，并用后缀和常数时间计算代价。

做法

补定义 $x_0=0$。最终首都在 $x_i$ 时的候选代价为

$$(a+b)x_i+b\left(\sum_{j=i+1}^{n}x_j-(n-i)x_i\right).$$

其中 $i=0$ 表示从不迁都。预处理坐标后缀和，枚举 $0\le i<n$ 并取最小值。没有必要在全部征服完成后迁到 $x_n$。

正确性证明

固定最终首都 $x_i$。在到达它之前，依次从当前首都征服下一个将迁往的王国再迁都，每段距离同时支付 $b$ 与 $a$，总距离望远镜求和为 $x_i$，故前缀代价为 $(a+b)x_i$。此后不再迁都，从 $x_i$ 征服每个右侧王国的代价总和正是公式第二项。

任意策略都有一个最后首都位置，且同一最终位置下上述顺序不劣，因此枚举覆盖某个最优策略。对所有位置取最小即为全局最优。

复杂度分析

时间复杂度为 $O(n)$，空间复杂度为 $O(n)$；答案必须使用 64 位整数。

子任务说明

• $n\le12$ 时枚举每次征服后是否迁都。
• $n\le3000$ 时枚举最终首都并逐个扫描右侧王国。
• 满数据用后缀和常数时间计算每个候选。