2019牛客多校第二场F – Partition problem

题目链接:2019牛客多校第二场F

把$2n$个人分成$n+n$两组,那么一共是${2n \choose n}$种情况,如果每一次都暴力计算竞争力总和,那么每一次的时间复杂度将是$O(n^2)$,总时间复杂度是$O({\rm C}_{2n}^{n} \times n^2)$,对于$n \leq 14$这个数据范围来说是过不去的。

考虑如何惰性计算这个竞争力总和,也就是说从状态$A$转移到状态$B$的时候根据状态的变化来计算贡献,这是一个常用的思路。

起初,我尝试讨论第$i$个元素是被分到哪一组,元素$x$加入$A$组对总和的贡献就是$\sum_{i \neq x} v_{ix}$,加到一个变量里求和即可,渐进时间复杂度$O({\rm C}_{2n}^{n} \times n)$,但是可能由于姿势不当TLE了。后来在题解中看到了一种思路类似的解法——算贡献的时候不用加,用减。假设当前没有分组的变量的竞争值就是$\sum_{i=1}^{n} \sum_{j = i+1}^{n} v_{ij}$,每次将一个元素分到某一组后,这个元素和原来这个组里的所有元素的贡献需要减去,那么在$n+n$全分配完之后得到的这个变量的值就是还没有被“割断”的“边”。这样做有个好处就是有一个可以减枝的条件:如果当前还没有被“割断”的“边”的总和已经小于当前的最大值了,这条路就没有必要继续枚举了,所以在同是$O({\rm C}_{2n}^{n} \times n)$的复杂度的情况下,这个算法快了很多,1676/4000ms。

 

说点什么

avatar
50
  Subscribe  
提醒