Codeforces 261B Maxim and Restaurant 概率,期望

文章目录

题意算法

题意

$给一个序列a,求a的排列的前面x个数之和小于或者等于p的x的期望.$

算法

$dp[i][j][k]$表示前$i$个人中$j$个人的体重和等于$k$的概率. 转移时枚举$i$,$j$,$k$,如果$k\ge p[i]$我们就可以加上这个人的体重. 如果我们不加这个人的体重,那这个概率就等于之前的人数选择这么多人的概率. dp[i][j][a]+=dp[i-1][j][a]. 但是显然这样做重复了. 对于$dp[n][i][j]$来说,从$n$个里选$i$个等于$j$的期望算了$C_n^i$次,所以答案要除上这个值. 最后的结果就是${\sum }_{i=1}^n{\sum }_{j=1}^p\frac{dp[n][i][j]}{C_n^i}$.

#include<bits/stdc++.h> //Ithea Myse Valgulious namespace chtholly{ typedef long long ll; #define re0 register int #define rel register ll #define rec register char #define gc getchar //#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?-1:*p1++) #define pc putchar #define p32 pc(' ') #define pl puts("") /*By Citrus*/ char buf[1<<23],*p1=buf,*p2=buf; inline int read(){ int x=0,f=1;char c=gc(); for (;!isdigit(c);c=gc()) f^=c=='-'; for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0'); return f?x:-x; } template <typename mitsuha> inline bool read(mitsuha &x){ x=0;int f=1;char c=gc(); for (;!isdigit(c)&&~c;c=gc()) f^=c=='-'; if (!~c) return 0; for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0'); return x=f?x:-x,1; } template <typename mitsuha> inline int write(mitsuha x){ if (!x) return 0&pc(48); if (x<0) pc('-'),x=-x; int bit[20],i,p=0; for (;x;x/=10) bit[++p]=x%10; for (i=p;i;--i) pc(bit[i]+48); return 0; } inline char fuhao(){ char c=gc(); for (;isspace(c);c=gc()); return c; } }using namespace chtholly; using namespace std; typedef double db; const int aoi=1018; db dp[55][55][55],c[55][55]; int p[aoi]; /**/ int main() { int i,j,k,a,n; read(n); for (i=0;i<=50;++i) for (j=0;j<=i;++j) c[i][j]=!j?1:c[i-1][j]+c[i-1][j-1]; for (i=1;i<=n;++i) p[i]=read(); for (read(k),i=0;i<=50;++i) **dp[i]=1; // dp[i][0][0]=1初始化. for (i=1;i<=n;++i) { for (j=1;j<=n;++j) { for (a=1;a<=k;++a) { if (a>=p[i]) dp[i][j][a]+=dp[i-1][j-1][a-p[i]]; dp[i][j][a]+=dp[i-1][j][a]; } } } db llx=0; for (i=1;i<=n;++i) for (j=1;j<=k;++j) llx+=dp[n][i][j]/c[n][i]; printf("%.9lf",llx); }