【算法学习笔记】max-min容斥 极值反演

发布时间 2023-08-23 13:40:20作者: caiyuyang

max-min容斥(极值反演)即为下式;

\[\begin{equation} \max\{S\}=\sum_{T\subseteq S}(-1)^{|T|+1}\min\{T\}\label{aa} \end{equation} \]

\[\begin{equation} \min\{S\}=\sum_{T\subseteq S}(-1)^{|T|+1}\max\{T\}\label{ab} \end{equation} \]

证明:证明 \(\ref{aa}\) 式即可,\(\ref{ab}\) 同理。