[noip模拟赛] 礼物gift

Description

夏川的生日就要到了。作为夏川形式上的男朋友,季堂打算给夏川买一些生日礼物。

商店里一共有种礼物。夏川每得到一种礼物,就会获得相应喜悦值Wi(每种礼物的喜悦值不能重复获得)。
每次,店员会按照一定的概率Pi(或者不拿出礼物),将第i种礼物拿出来。
季堂每次都会将店员拿出来的礼物买下来。没有拿出来视为什么都没有买到,也算一次购买。
众所周知,白毛切开都是黑的。所以季堂希望最后夏川的喜悦值尽可能地高。
求夏川最后最大的喜悦值是多少,并求出使夏川得到这个喜悦值,季堂的期望购买次数。

Input

第一行,一个整数N,表示有N种礼物。
接下来N行,每行一个实数Pi和正整数Wi,表示第i种礼物被拿出来的概率和可以获得喜悦值。

Output
第一行,一个整数表示可以获得的最大喜悦值。
第二行,一个实数表示获得这个喜悦值的期望购买次数,保留3位小数。
Sample Input
3
0.1 2
0.2 5
0.3 7
Sample Output
14
12.167

HINT

对于10%的数据,N=1N=1
对于30%的数据,N≤5N\leq 5
对于100%的数据, N≤20N\leq 20 , 0<Wi≤1090 < W_{i} \leq 10^{9} , 0<Pi≤10 < Pi ≤ 1 且 ∑Pi≤1\sum P_{i} \leq 1

Source

N≤20N\leq 20 首先应该考虑用状压(其实这不是最难的一个地方)
关键在于推公式

在做思考这个题之前先想一个比较简单的问题：

平均需要扔多少次硬币才能够得到连续2个正面？

要先知道一般的期望计算的方法：元素的期望=元素的概率*元素的值
这个问题应该把平均的次数看成元素的值
可以设平均需要\(T\) 次才能得到连续2个正面
写出方程：
T=(1−p)(1+T)+p(1−p)(2+T)+2p2T=\left(1-p \right)\left(1+T \right)+p\left(1-p \right)\left(2+T \right)+2p^{2} (pp为投到正面的概率)
中间的(1−p)(1+T)\left(1-p \right)\left(1+T \right)代表如果第一次投到反面，那么还平均需要TT次才能得到连续2个正面所以需要1+T1+T次
p(1−p)(2+T)p\left(1-p \right)\left(2+T \right)代表如果第一次投到正面第二次投到反面那么还平均需要TT次才能得到连续2个正面所以需要2+T2+T次
2p22p^{2}代表如果两次都投中的期望
化解即可求得这个问题的解

再来看这个题目
用kk是一个二进制数表示买到了哪些物品 例如:k=101101k=101101 表示买到了第1,3,4,6个物品
ff表示期望值
假设已经求到了所有比kk少一个物品的期望，k′k'表示比kk少一个物品的二进制数，pp为每个物品拿出来的概率，ii表示从k′k'这个状态还需要买第ii个物品就可以变成kk，那么公式可以写成:

fk=∑pi⋅fk′+(1−∑pi)fk+1f_{k}=\sum p_{i}\cdot f_{k'}+(1-\sum p_{i})f_{k}+1

∑pi⋅fk′\sum p_{i}\cdot f_{k'}表示已经买到了k′k'现在再买第ii个物品就可以达到kk的期望

(1−∑pi)fk(1-\sum p_{i})f_{k}表示之前kk里面包含的物品一个都没有买到，那么需要再买fkf_{k}次才能卖完kk个
最后加一个1表示当前再买一个
移项化解可得：

∑pi⋅fk=∑pi⋅fk′+1\sum p_{i}\cdot f_{k}=\sum p_{i}\cdot f_{k'}+1

fk=∑pi⋅fk′+1∑pif_{k}=\frac{\sum p_{i}\cdot f_{k'} + 1}{\sum p_{i}}

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <cstring>
#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;
typedef long long ll;
const int maxn=21;

double dp[1<<22],p[maxn];
int n,w[maxn];

int main()
{
    //freopen("gift.in","r",stdin);
    //freopen("gift.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%lf%d",p+i,w+i);
    ll ret=0;
    for(int i=1;i<=n;++i) ret+=1LL*w[i];
    printf("%lld\n",ret);
    double sigma=0;
    for(int k=1;k<(1<<n);++k)
    {
        sigma=0;
        for(int i=1;i<=n;++i)
            if(((1<<(i-1))&k)) {
                sigma+=p[i]*1.0;
                dp[k]+=p[i]*dp[k^(1<<(i-1))]*1.0;
            }
        if(sigma==0) continue;
        dp[k]=((dp[k]+1.0)*1.0)/(sigma*1.0);
    }
    printf("%.3lf\n",dp[(1<<n)-1]);
    return 0;
}