UOJ422. 【集训队作业2018】小Z的礼物 [min-max容斥,插头DP]

时间:2021-06-02 21:48:06

UOJ

思路

由于没有代码和AC记录的支撑,以下思路可能有错。

看到全部取完,大概可以想到min-max容斥。

由于期望的表达式里面合法方案的个数是在分母里面的,所以可以想到把它记录在状态里。

然而由于我菜,一开始只想到逐列DP,于是复杂度炸了……

考虑插头DP:设\(f_{i,j,S,k}\)表示当前做到\((i,j)\),轮廓线上的状态是\(S\),已经有\(k\)个取到礼物的方案,带容斥系数的方案数。

转移想必乱搞就行了?

代码

咕咕咕