正解:期望

解题报告:

先放下题意,,,已知有总共有$n$张卡片,每次有$p_i$的概率抽到第$i$张卡,求买所有卡的期望次数

$umm$看到期望自然而然想$dp$?

再一看,哇,$n\leq 20$,那不就,显然考虑状压$dp$?

转移也很$easy$鸭,设$f_{s}$表示已经获得的卡片状态为$s$时候的期望次数

不难得到转移方程,$f_s=\sum_{i\notin{S}}f_{s|\{i\}}\cdot p_i+(1-\sum_{i\notin{S}}p_i)\cdot f_s+1$

(挺显然的就只瞎解释下,,,就状态是$s$之后,再抽一次,有可能抽到需要的$i$,就是$f_{s|\{i\}}\cdot p_i$,也可能没抽到需要的$i$,就是$(1-\sum_{i\notin{S}}p_i)\cdot f_s$,然后不管抽没抽到反正都抽了一次所以还要+1,就$over$辣!

变形下就是$\sum_{i\notin{S}}p_i\cdot f_s=\sum_{i\notin{S}}f_{s|\{i\}}\cdot p_i+1$

再除过去就$get$了$f$的转移方程辣

然后就做完辣,,,?

放下代码趴$QwQ$

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

#define my(i,x,y) for(ri i=x;i>=y;--i)

const int N=;

int n,tot;

double f[<<N],p[N];

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        rp(i,,n-)scanf("%lf",&p[i]);

        tot=(<<n)-;f[tot]=;

        my(i,tot-,)

        {

            double sum=;f[i]=;

            rp(j,,n-)if(~i&(<<j))f[i]+=p[j]*f[i|(<<j)],sum+=p[j];

            f[i]=(f[i]+)/sum;

        }

        printf("%.4lf\n",f[]);

    }

    return ;

}

昂对了,$attention$,这题$Sample Output$是三位小数嘛,但是$output$里说了,当相差小于等于1$e$-4的时候是可以接受的,也就是说输出要保留到四位小数昂$QwQ$!

$upd$:

$get$了一个神奇的容斥,,,$orzorz$神仙$hl$

尝试自己理解了下结果好像失败辽,,,

先写下结论

就,$min-max$容斥中提出了这样一个式子:$E(\max\{x_1,x_2...x_n\})=\sum_{S}(-1)^{|S|+1}E(\min_{i\in{S}}\{x_i\})$

然后此处如果定义$x_i$表示第$i$张牌第一次出现的轮号,那其实就相当于这个$ E(\max\{x_1,x_2...x_n\})$指的就是最后的$ans$了

然后又有$\min_{i\in{S}}x_i=\frac{1}{\sum_{i\in{S}}p_i}$

然后用$dfs$枚下子集

就做完辣,,,?复杂度要好看很多呢$QwQ$

(神仙$hl$手推出了$min-max$容斥,,,太神了%%%

$code$就不放了知道思想的话具体实现还是挺$easy$的,有兴趣的去神仙$hl$的博客看趴,,,$QAQ$

昂然后关于这个$min-max$容斥,,,$gql$可能会尝试瞎证下$QwQ$,,,大概会新开篇博客,等下写完放链接趴$QAQ$←对不起咕了$TT$

随机推荐

H3C SSH配置例子
20190528-JavaScriptの打怪升级旅行 { 语句 [ 赋值，数据 ] }
写在前面的乱七八糟:今天考了试,emmm很基础的题,还是Mrs房的面试题让人绝望啊┓( ´∀` )┏,补了很多知识,很综合的题,坑也很多,总的来说,查漏补缺,其实是啥都缺~ 今天打的小BOSS主要是数 ...
什么是HOOK技术
https://zhidao.baidu.com/question/50557962.html HOOK技术是Windows消息处理机制的一个平台,应用程序可以在上面设置子程序以监视指定窗口的某种消息 ...
H3C DCC的特点
ip2long与long2IP 分析
<?php $ip='47.93.97.127'; $long=sprintf("%u",ip2long($ip));//string(9) "794648959& ...
Python--day28--摘要算法
摘要算法:
洛谷P1280 尼克的任务题解动态规划/最短路
作者:zifeiy 标签:动态规划.最短路题目链接:https://www.luogu.org/problem/P1280 题目大意: 有k个任务分布在第1至n这n个时间点,第i个任务的于第 \(P ...
jackson java转json hibernate懒加载造成的无限递归问题
@JsonIgnore @JsonFilter @JsonBackReference @JsonManagedReference @JsonIgnoreProperties jackson中的@Jso ...
Python--day46--分组（看了别人博客掌握的）
原文链接:https://www.cnblogs.com/snsdzjlz320/p/5738226.html group by group by + group_concat() group by ...
Codeforces Round #186 (Div. 2)
A. Ilya and Bank Account 模拟. B. Ilya and Queries 前缀和. C. Ilya and Matrix 考虑每个元素的贡献. 边长为$2^n$时,贡献为最 ...

秒客网

$HDU$ 4336 $Card\ Collector$ 概率$dp$/$Min-Max$容斥

正解:期望

解题报告:

随机推荐

相关文章