因为这是远古题目,所以根据现在的评测机速度,用 \(O(nq)\) 的做法也是可以过的。
也就是说,我们可以每次操作直接修改对应位置上的数字,然后设计一种 \(O(n)\) 的算法求解答案。
这道题类似资源分配型动态规划,所以我们可以设 \(dp_i\) 表示分配前 \(i\) 个人的答案。
直接写是不行的,我们根据排序不等式先把 \(a\) 和 \(b\) 数组排序,然后进行转移。首先有一个结论,在当前的状态下,\(i\) 只能由 \([i-2,i]\) 中间的状态转移过来,因为我们要求人和马连边以后逆序对数量最少,但是因为题目限制,所以 \([i-2,i]\) 之间的状态我们都需要考虑。
所以我们分四种情况转移,画个图方便理解(图很丑谅解一下):
然后根据上图我们可以列出来四个方程:
\[dp_i=\max \left\{ \begin{array}{lc} dp_{i-1}+a_ib_i&ch(i,i)\\ dp_{i-2}+a_ib_{i-1}+a_{i-1}b_i&ch(i,i-1)~and~ ch(i-1,i)\\ dp_{i-3}+a_ib_{i-2}+a_{i-2}b_{i-1}+a_{i-1}b_{i}&ch(i-2,i-1)~and~ch(i-1,i)~and~ch(i,i-2)\\ dp_{i-3}+b_ia_{i-2}+b_{i-2}a_{i-1}+b_{i-1}a_{i}&ch(i-2,i)~and~ch(i,i-1)~and~ch(i-1,i-2)\\ \end{array} \right. \]其中 \(ch(i,j)\) 的含义是 \(a_i\) 和 \(b_j\) 可以匹配。
为了维护 \(ch\) 这个条件,我们不妨存储 \(a\) 数组和 \(b\) 数组每个元素的编号,并设立一个新数组 \(fa\),然后令 \(fa_i\) 表示 \(a_i\) 对应的 \(b\) 的编号。
然后我们可以给出 \(ch\) 的代码。
bool ch(int x,int y)
{
return fa[a[x].id]!=b[y].id&&x>0&&y>0;
}
每次修改的时候对于修改的两个位置 \(x,y\) 我们直接交换 \(fa_x\) 和 \(fa_y\) 即可。
然后这道题就结束了。
标签:ch,CF573D,题解,Bear,fa,数组,ib,我们,dp From: https://www.cnblogs.com/Lydic/p/18431592