题目链接：计算机软件能力认证考试系统
小林在玩一个抽卡游戏，其中有?n?种不同的卡牌，编号为?1?到?n。每一次抽卡，她获得第?i?种卡牌的概率为?pi。如果这张卡牌之前已经获得过了，就会转化为一枚硬币。可以用?k?枚硬币交换一张没有获得过的卡。
小林会一直抽卡，直至集齐了所有种类的卡牌为止，求她的期望抽卡次数。如果你给出的答案与标准答案的绝对误差不超过?10?4，则视为正确。
提示：聪明的小林会把硬币攒在手里，等到通过兑换就可以获得剩余所有卡牌时，一次性兑换并停止抽卡。
输入格式
从标准输入读入数据。
输入共两行。第一行包含两个用空格分隔的正整数?n,k，第二行给出?p1,p2,…,pn，用空格分隔。
输出格式
输出到标准输出。
输出共一行，一个实数，即期望抽卡次数。
样例1输入
2 2
0.4 0.6Data
样例1输出
2.52?
分析:这显然是一道概率DP题目，我么可以令f[i][j]表示当前收集卡牌状态为i且当前有k个硬币距离集齐所需要次数的期望，那么答案显然就是f[0][0]，我们用记忆化搜索去查找f[0][0],我们下面进行分析搜索函数的写法：
首先来看一下递归终止条件，不妨假设有n张不同的卡牌，每k个硬币可以换一张卡牌，肯定是s全为1也就是s的二进制表示中含有n个1时退出，或者s二进制表示中的0的个数乘以k小于等于t，也就是说我们现在所拥有的硬币可以把缺少的牌全部换回来，这就是我们的递归终止条件了，递归体就比较容易写了，我们看看f[s][k]可以更新至哪些状态，首先可以更新至f[s][k+1]，也就是说我们抽到了已经存在的一张牌自动转换为一个硬币，还有就是f[s|(1<<i)][k]，也就是说我们抽到了我们之前不含有的一张牌，硬币数目不变，但是我们的状态会发生变化，还有需要注意的一点是不要忘记乘以其对应的概率p[i]，再加上当前抽取牌所消耗的一次机会，这一部分我们是在递归函数中用for循环枚举的。考虑到这些这道题目基本上就解决了。
下面是代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
double f[1<<20][103];//f[i][j]表示当前收集卡牌状态为i且当前有k个硬币距离集齐所需要次数的期望
double p[20];
int n,k;
double dp(int s,int t)//fp(s,t)返回当前收集卡牌状态为s且当前有t个硬币距离集齐所需要次数的期望
{
int cnt=0;
for(int i=0;i<n;i++)
if(s>>i&1) cnt++;
if((n-cnt)*k<=t) return 0;//可以用硬币直接交换
if(f[s][t]) return f[s][t];
for(int i=0;i<n;i++)
{
if(s>>i&1)
f[s][t]+=p[i]*(dp(s,t+1)+1);
else
f[s][t]+=p[i]*(dp(s|(1<<i),t)+1);
}
return f[s][t];
}
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)
scanf("%lf",&p[i]);
printf("%.10lf",dp(0,0));
return 0;
}