Min-Max 容斥

时间：2021-05-24 22:53:04 阅读：21 评论：0 收藏：0 [点我收藏+]

\[\max(S)=\sum\limits_{T\subseteq S}(-1)^{|T|-1}\min(T) \\min(S)=\sum\limits_{T\subseteq S}(-1)^{|T|-1}\max(T) \]

有亿亿丶丶简单，但是有人不会？？？

设 \(|T|=n\)，\(\max\) 为 \(T\) 集合中最大元素

考虑 \(|T|=1\) 的情况，此时我们需要的仅仅是一个值，但是我们加上了 \(n\) 个值

然后我们就要考虑在 \(|T|=2\) 时去除

如何去除呢？不难想到就是利用 \(T=\{\max,i\}\) 去除，\(i\) 是我们要去除的元素

但是此时会多减，如何加上呢？这就是在 \(|T|=3\) 的时候的工作了

以此类推，就证得了

\[\max(k,S)=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min(T) \]

仿照上例显然，留给读者思考

~~确实不难啊不要打我qwq~~

没写，咕咕咕

原文：https://www.cnblogs.com/zythonc/p/14805400.html

踩

(0)

评论一句话评论（0）

分享档案

更多>