礼物

时间限制: 1 Sec 内存限制: 256 MB

题目描述

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

商店里一共有种礼物。夏川每得到一种礼物，就会获得相应喜悦值Wi（每种礼物的喜悦值不能重复获得）。

每次，店员会按照一定的概率Pi（或者不拿出礼物），将第i种礼物拿出来。季堂每次都会将店员拿出来的礼物买下来。没有拿出来视为什么都没有买到，也算一次购买。

众所周知，白毛切开都是黑的。所以季堂希望最后夏川的喜悦值尽可能地高。

求夏川最后最大的喜悦值是多少，并求出使夏川得到这个喜悦值，季堂的期望购买次数。

输入

第一行，一个整数N，表示有N种礼物。

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

输出

第一行，一个整数表示可以获得的最大喜悦值。

第二行，一个实数表示获得这个喜悦值的期望购买次数，保留3位小数。

样例输入

样例输出

14
12.167

提示

对于10%的数据，N = 1
对于30%的数据，N ≤ 5
对于100%的数据，N ≤ 20 ，0 < Wi ≤ 10^9 ，0 < Pi ≤ 1且∑Pi ≤ 1

注意：本题不设spj

题解

第一问是没有什么用啊，只要概率不为0是一定要买到的，需要做的只有第2问。再看一看数据范围，居然是个状压?于是十分兴奋，感觉很新奇。但是考试的时候没推出式子，几乎没有拿分，所以即使A掉了第二题也不算很好。

用1表示还没有的礼物，我们的目标是从0推到全集。f[i]=∑(f[j]*p[k])+(1-∑p[q])*f[i]+1，其中j状态是i状态的子集，k就是i和j相差的那一位，q是i中有的元素。前半段表示从j状态转移到k状态的期望，后半段表示i状态转移回自己的期望，因为步数多了一步所以+1。等式的两边可以消去f[i],再移项就变成了(∑p[q])*f[i]=∑(f[j]*p[k]),(∑p[q]是f[i]的系数，f[i]+=p[q]*f[i])这样一来只要枚举每一个状态中的所有1就可以递推出f[(1<<n)-1]了。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int sj=25;
const int ef=1050000;
int n,temp,rd[ef],tp,op;
long long w[sj],ans;
double p[sj],f[ef],s,q;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
       scanf("%lf%lld",&p[i],&w[i]);
       if(p[i]!=0.0)  ans+=w[i];
       else i--,n--;
    }
    printf("%lld ",ans);
    temp=(1<<n)-1;
    for(int i=1;i<=temp;i++)
    {
      s=q=0.0;
      for(int j=0;j<n;j++)
        if(i&(1<<j))  
        {
          s+=p[n-j];
          q+=p[n-j]*f[i&(~(1<<j))];
        }
      f[i]=(q+1)/s;
    }
    printf("%.3lf",f[temp]);
    return 0;
}

gift