BZOJ 3622 已经没有什么好害怕的了

发布于 2017-11-20  181 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3622

题意:两个队伍比赛,每个人有独一无二的战斗力,每队 n 个人,两两配对作战,战斗力高者得一分,求第一队比第二队高 k 分的方案数。


离散化所有人。

首先有一个朴素的\(O(n^3)\) 做法:将两队接起来后排序,\(dp_{i,j,k}\) 表示考虑到第 i 个人,第一队得 j 分,第二队得 k 分的方案数。

显然对于每个人,有两个决策,要么打败一个以前的人,要么等着被以后的人打败。

其中,能打败多少个以前的人可以通过状态简单算出。

上述做法有 80 分,下面考虑正解。

单独考虑第一个队,预处理出第一队的每个人可以打败多少个第二队的人。

\(dp_{i,j}\) 表示考虑到第 i 个人,第一队得 j 分的方案数。状态被简化了,直接 DP 下去。转移的时候考虑要么击败一个人,要么先不管他。

最后考虑这样的状态:\(dp_{n,i}\),这代表第一个队的 n 个人有 i 个击败了第二队的人,其余暂时不管。

有\(g_i=dp_{n,i}*(n-i)!\),其中\(g_i\) 表示第一队至少得 i 分的方案数。

从后往前去重即可。

 


一个非常弱的准退役OIER