202109CSPT4收集卡牌

题意：有$n$种不同的卡牌,每一次抽卡获得第$i$种卡牌的概率为$pi$。如果这张卡牌已经获得，就会转化为一枚硬币。可以用$k$枚硬币交换一张没有获得过的卡。求获得所有种类的牌的概率。

#include<bits/stdc++.h>
using namespace std;
double dp[100][65636];//抽取层数,状态的概率 
double p[30];
int book[65636];
int n,k;
double dfs(int level,int state,int need)
{
    if((n-need)*k<=level-need)//层数大于剩余数*k就退出 
    return level;
    double ans=0;
    for(int i=0;i<n;i++)
	{
        if(book[i]==0)//没有选过这种卡牌 
		{
            book[i]=1;
            if(dp[level+1][state+(1<<i)]==0)
            dp[level+1][state+(1<<i)]=dfs(level+1,state+(1<<i),need+1);
            
			ans+=p[i]*dp[level+1][state+(1<<i)];
            book[i]=0;//树枝搜索结束后需要将标记清理，因为这是限制搜索应当一直向下 
        }
        else//重复选牌 
		{
            if(dp[level+1][state]==0)
            dp[level+1][state]=dfs(level+1,state,need);
            
			ans+=p[i]*dp[level+1][state];
        }
    }
    return ans;
}
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)cin>>p[i];
	double ans=dfs(0,0,0);
	printf("%.10lf\n",ans);
	return 0;
}