正解是状压dp,我硬搜,为什么只有10分?
//搜索与回溯
#include<bits/stdc++.h>
using namespace std;
int n,k;
double ans;
double p[20];//每种卡抽到的概率
int vis[20];//每个卡抽的数量
bool check()
{
int res=0,cnt=0;//硬币数,需要的卡
for(int i=1;i<=n;i++)
{
if(vis[i])//有这种卡
{
res+=vis[i]-1;
}
else cnt++;//没有
}
if(k*cnt<=res)//硬币够用
return 1;
else return 0;
}
void dfs(int x,double pp)//x表示已经选了几个了
{
if(check())
{
ans+=1.0*x*pp;
return ;
}
for(int i=1;i<=n;i++)
{
vis[i]++;
dfs(x+1,pp*p[i]);
vis[i]--;
}
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>p[i];
}
dfs(0,1.0);
printf("%.10lf",ans);
return 0;
}