题解

来源：Petrozavodsk Summer-2017. JOI TST 2012 Selection Problem G.

题意 有 $n$ 只袋鼠，每只袋鼠身体体积 $A_i$，口袋容积 $B_i$，袋鼠 $i$ 可以被塞进袋鼠 $j$，当且仅当 $A_i < B_j$，$j$ 不在其他袋鼠口袋里，$j$ 口袋内不包含其他袋鼠。你可以进行若干次这样的操作（注意袋鼠也是可以嵌套的），要求最终状态不存在有序对 $(i,j)$ 使得袋鼠 $i$ 可以被塞进袋鼠 $j$，问有多少种可能的最终状态。$n \leq 300$

题解 将袋鼠按照身体体积从大到小排序，定义 $dp[i][j][k]$ 表示已经考虑过前 $i$ 只袋鼠，其中将他们已经分成 $j$ 组，并且有 $k$ 只袋鼠是“危险袋鼠”，危险是指他们的口袋是空的，但是存在体积小于他们口袋大小并且还没有被装在别的袋鼠口袋中的袋鼠。转移分三种情况：

• 将第 $i+1$ 只袋鼠新开一组。这样之前所有口袋空余并且能装下这只袋鼠的袋鼠会成为所有的危险袋鼠。记能装下第 $i$ 只袋鼠的所有袋鼠个数是 $pre_i$，则 $dp[i+1][j+1][pre_{i+1}-(i-j)] \leftarrow dp[i][j][k]$
• 将第 $i+1$ 只袋鼠放进某个危险袋鼠的袋子里。危险袋鼠共有 $k$ 个选择，并且放完之后新的危险袋鼠恰为 $k-1$，故 $dp[i+1][j][k-1] \leftarrow k\cdot dp[i][j][k]$
• 将第 $i+1$ 只袋鼠放进某个非危险袋鼠的袋子里。能装下它的非危险袋鼠共有 $pre_{i+1} - (i-j) - k$ 只，放完之后新的危险袋鼠数量仍为 $k$，故 $dp[i+1][j][k] \leftarrow (pre_{i+1}-(i-j)-k)\cdot dp[i][j][k]$

显然可以 $O(n^2)$ 预处理出 $pre$ 数组。时间复杂度 $O(n^3)$。