题解

思路

分别把勇士和马按力量从小到大排序，力量相同者用原编号稳定打破平局。记排序后的力量为 $W_i,H_i$。若没有禁配限制，根据重排不等式，最大总力量为

当前第 $i$ 名勇士所拥有的马排名记为 $p_i$。无约束最优配对只会在 $p_i=i$ 时违反限制；这些位置称为坏位置。可以证明，最优合法排列只需把排名序列切成长度不超过 $3$ 的连续块：好位置可以独自成块，长度 $2$ 的块交换两匹马，长度 $3$ 的块选择两个三循环中损失较小者。所有坏位置都必须被长度 $2$ 或 $3$ 的块覆盖。

长度 $2$ 的块 $(i,i+1)$ 相对 $B$ 的损失为

长度 $3$ 的块枚举两个三循环即可得到 $C_3(i)$。

做法

算法一：全排列匹配

当 $n\le8$ 时，每次交换后枚举所有马的排列，过滤掉勇士骑到当前自有马的方案，直接计算最大乘积和。

算法二：每次重算线性 DP

令 $dp_i$ 为覆盖前 $i$ 个排名的最小损失。转移为：

• 若 $i$ 不是坏位置，可从 $dp_{i-1}$ 接一个长度 $1$ 的块；
• 从 $dp_{i-2}+C_2(i-1)$ 接一个长度 $2$ 的块；
• 从 $dp_{i-3}+C_3(i-2)$ 接一个长度 $3$ 的块。

每次交换只改变两个勇士排名上的坏位置，但中档算法直接 $O(n)$ 重算，答案为 $B-dp_n$。

算法三：最小加矩阵线段树

把状态写成 $(dp_i,dp_{i-1},dp_{i-2})$。第 $i$ 个位置对应一个 $3\times3$ 最小加矩阵，第一行依次放长度 $1,2,3$ 转移代价，后两行负责平移状态。区间矩阵按位置顺序做最小加乘法。

交换两位勇士的自有马排名后，只需重新判断两个位置是否为坏位置，并在线段树上修改对应叶矩阵。根矩阵作用于初始状态 $(0,+\infty,+\infty)$，其 $(0,0)$ 元即 $dp_n$。

正确性证明

Monge 交换不等式表明，若一个合法排列存在跨越且互不相交的逆序边，消除交叉不会降低总力量。反复消除后，每个不可再分的非平凡连续块只需考虑长度 $2$ 的交换或长度 $3$ 的三循环；更长循环总能拆成这些块且损失不增。坏位置不能使用恒等配对，好位置可以单独保留，因此上述分块 DP 恰好枚举全部最优候选。矩阵只是该递推的等价表示，线段树维护乘积不改变递推结果，所以每次输出均为合法分配的最大总力量。

复杂度

三档算法每次操作的复杂度分别为 $O(n!\,n)$、$O(n)$ 与 $O(\log n)$。满分算法预处理 $O(n\log n)$，空间复杂度 $O(n)$。