首页 > 其他 > 详细

min-max容斥

时间:2020-07-29 10:29:35      阅读:61      评论:0      收藏:0      [点我收藏+]

min-max容斥
min-max容斥是指给定集合\(S\),设\(max(S)\)表示\(S\)中的最大值,\(min(S)\)表示集合中的最小值,则有

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

相关题目
hdu4336 Card Collector
\(n\)件物品,每一秒有可能获得其中的一件物品\(i\),概率为\(p_i\),求获得所有物品的期望时间。

\(max(S)\)表示第一次获得\(S\)中最后一种卡片的期望时间,\(min(S)\)表示第一次获得\(S\)中第一种卡片的期望时间
其中\(min(S)=\frac{1}{\sum_{i\in T}P_i}\)
时间复杂度\(O(2^n)\)

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include<cmath>
#include<ctime>
#include<algorithm>
#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define pi acos(-1.0)
#define eps 1e-6
#define lowbit(x) x&(-x)
using namespace std;

const int maxn=25;
int n;
double p[maxn],ans;

void dfs(int id,int k,double sum){
    if(id==n){
        if(sum<eps) return;
        if(k&1) ans+=1/sum;
        else ans-=1/sum;
        return;
    }
    dfs(id+1,k+1,sum+p[id]);
    dfs(id+1,k,sum);
}

int main(){
    while(scanf("%d",&n)!=EOF){
        for(int i=0;i<n;i++) scanf("%lf",&p[i]);
        ans=0.0;
        dfs(0,0,0.0);
        printf("%.4f\n",ans);
    }
    return 0;
}

min-max容斥

原文:https://www.cnblogs.com/fxq1304/p/13394768.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!