min-max容斥：
给定集合S，设max{S}为S中的最大值，min{S}为集合S中的最小值。
那么我们可以得到：
max{S}=∑T?S(?1)|T|+1min{T}
证明： 咕咕咕
对于期望来说，min-max容斥同样适用
E(max{x1,x2...xn})=∑S(?1)|S|+1E(min i∈S{xi})
例题：hdu 4336
这道题可以用状压dp来做
但是min-max有更优秀的空间复杂度O(n)
dfs枚举子集来计算 E(min{T})=1∑i∈Tpi
// min-max 容斥 #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> #include<stack> #include<queue> using namespace std; typedef long long ll; const int maxn = 25; const double eps = 1e-7; int n; double ans,p[maxn]; void dfs(int d,double tot,double opt){ if(d==n){ if(tot>eps) // 很关键!! ans+=opt/tot; return; } dfs(d+1,tot+p[d],-opt); dfs(d+1,tot,opt); } ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<‘0‘ || ch>‘9‘){ if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘ && ch<=‘9‘){ s=s*10+ch-‘0‘; ch=getchar(); } return s*f; } int main(){ while(scanf("%d",&n)!=EOF){ for(int i=0;i<n;i++) scanf("%lf",&p[i]); ans=0; dfs(0,0,-1); // 枚举子集 printf("%.4lf\n",ans); } return 0; }
原文：https://www.cnblogs.com/tuchen/p/10351047.html