ARC207A - Affinity for Artifacts

考虑刻画问题为另一个形式：

设 $W=(\sum a_i) - X$ ，计数有多少个长度为 $n$ 的排列 $p$ ，使得 $\sum \min(a_i,p_i-1)\ge W$ 。

显然当

W\ge O(n^2)

时无解。

对排列计数比较困难，但是实际上我们可以把它转化为一个二分图匹配问题。

左部点是

\{a_1,a_2,\cdots,a_n\}

，右部点是

\{0,1,\cdots,n-1\}

。匹配的边权为两边的点权的

\min

，相当于计数有多少对完美匹配，使得所有边权和

\ge W

。

把左部点

(a_i,0)

和右部点

(i-1,1)

放在一起从大到小排序，设计状态

f_{i,j,k,l}

表示考虑前

i

个点，有

j

个左部点还没有匹配，

k

个右部点还没有匹配，当前已经匹配的边权和为

l

。

显然我们每次遇到一个左部点

(a_i,0)

，可以选择

k\gets k-1

，产生

a_i

的贡献；或者

j\gets j+1

，使得未匹配左部点数量增加。

状态数看似是

O(n^5)

的，转移是

O(1)

的。但实际上有值的状态只有

O(n^4)

个，所以复杂度是

O(n^4)

。

文章操作