这个屌丝很懒，什么也没留下！

[集训队作业2018]小Z的礼物（min-max容斥，插头dp）_小 z 的礼物

作者：编程革命者 | 2024-01-31 15:04:18

这种求 “取到所有物品的期望时间” 的题一般都用 $m i n - m a x$ 容斥 解决：
设 $t (i, j)$ 为取到格子 $(i, j)$ 的期望时间，集合 $S=\cup_{c(i,j)='*'}\{t(i,j)\}$
那么根据 $m i n - m a x$ 容斥有： $\max(S) = \sum_{T\subseteq S, T \neq \varnothing} (-1)^{|T|-1}\min(T)$

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/50912