设$f[i][j][k]$表示前$i$个物品买了$j$个，消耗$k$个钻石，最少花多少钱，可以通过简单的DP求出。

枚举拥有的钻石数以及最多能购买的物品数的下界，那么钱数的下界是定值。

将$n$个箱子折半搜索，按钻石数分组并排序，枚举左半边每种方案，在右半边双指针求出总概率即可。

时间复杂度$O(nm2^{\frac{n}{2}}+nm^2)$。

 

#include
     
      #include
      
       const int N=33,inf=~0U>>2;int T,n,m,lim,i,j,k,f[N][N][N],ca[N],cb[N];double p[N],ans;struct P{int x;double p;P(){}P(int _x,double _p){x=_x,p=_p;}}a[N],A[N][33000],B[N][33000];struct E{int c,d;}b[N];inline bool cmp(const P&a,const P&b){return a.x
       
        b)a=b;}void dfsl(int x,int y,int z,double p){  if(x==lim){    A[y][++ca[y]]=P(z,p);    return;  }  dfsl(x+1,y,z+a[x].x,p*a[x].p);  dfsl(x+1,y+1,z,p*(1.0-a[x].p));}void dfsr(int x,int y,int z,double p){  if(x==n){    B[y][++cb[y]]=P(z,p);    return;  }  dfsr(x+1,y,z+a[x].x,p*a[x].p);  dfsr(x+1,y+1,z,p*(1.0-a[x].p));}inline double cal(int x,int y,int z){  if(z>=inf)return 0;  int n=ca[x],m=cb[y],i;double p=0,ret=0;  if(!n||!m)return 0;  for(i=1;i<=n;i++){    while(m&&A[x][i].x+B[y][m].x>=z)p+=B[y][m--].p;    ret+=A[x][i].p*p;  }  return ret;}int main(){  for(scanf("%d",&T);T--;printf("%.4f\n",ans)){    scanf("%d%d",&n,&m);lim=n/2;    for(i=0;i
        
         1)std::sort(A[i]+1,A[i]+ca[i]+1,cmp);      if(cb[i]>1)std::sort(B[i]+1,B[i]+cb[i]+1,cmp);    }    ans=p[m+1]=0;    for(i=0;i<=n;i++)for(j=m;j;j--){      p[j]=0;      for(k=0;k<=lim&&k<=i;k++)p[j]+=cal(k,i-k,f[m][j][i]);      ans+=(p[j]-p[j+1])*j;    }  }  return 0;}