https://www.bnuoj.com/v3/contest_show.php?cid=9147#problem/D
【题意】
为了集齐n张卡片，必须要买多少袋零食？题目给定每种卡片出现在零食中的概率。
【思路】
以2张卡片为例，dp[00]表示要从00->11需要的零食数，则初始化dp[11]=0,dp[00]就是我们要求的。
那么在dp[00]这个状态，我们需要买一袋零食。
如果这袋零食有卡片1，那么后续我们还要操作dp[01];
如果这袋零食有卡片2，那么后续我们还要操作dp[10];
如果这袋零食没有卡片，那么后续我们还要操作dp[00]。
所以dp[00]=(1+p[0]*dp[01]+p[1]*dp[10]+(1-p[0]-p[1])*dp[00])
由此类推
dp[0...0]=(1+sgm(p[k]*dp[i|1<<k])+(1-sgm(p[k]))*dp[0.....0])
题目给的n最多是20,所以可以用状压dp
常用的状压dp技巧：
i&(1<<k):看i的第k位是0还是1
if(!(i&(1<<k))) i|=(1<<k)
把i的第k位从0变成1
尤其要注意<<的优先级。
【Accepted】
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
int n;
const int maxn=;
const int inf=0x3f3f3f3f;
double a[maxn];
double dp[<<];
int main()
{
while(~scanf("%d",&n))
{
memset(dp,,sizeof(dp));
for(int i=;i<n;i++)
{
scanf("%lf",&a[i]);
}
dp[(<<n)-]=0.0;
for(int i=(<<n)-;i>=;i--)
{
double phi=0.0;
for(int k=;k<n;k++)
{
if((i&(<<k)))
{
continue;
}
dp[i]+=a[k]*dp[i|(<<k)];
phi+=a[k];
}
dp[i]=(dp[i]+1.0)/phi;
}
printf("%.6lf\n",dp[]); }
return ;
}