IBM Ponder This #012 · 1999 年 4 月

有 $N$ 块石头，编号为 $1$ 到 $N$，在河岸边排成一列，但顺序不正确。

Wally 的石块置换公司每次服务固定收费 5 欧元：它会接受一份互不重叠的石块对列表，并交换列表中每一对石块。无论列表中有一对还是多对，收费相同；但同一块石头不能在同一次服务中出现两次。

对给定的 $N$ 和初始排列，若以最有效的方式安排对 WRP 的调用，那么固定 $N$ 时最坏情况下最多需要付多少钱？

解答

认真尝试后再打开

题解

待补充。