cf期望概率专题

傷城~ 2023-10-12 08:22 151阅读 0赞

cf1009E：求到第i段期望和的比较困难，但是单独求每段的期望是比较容易的，所以单独对每段求和，然后累计总和

E[i]=1/2*a1+1/4*a2+…+1/2^(i-1)*ai-1+1/2^(i-1)*ai，E[1-n]是可以递推的

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  5. const int maxn = 1e6+10;
  6. const ll mod = 998244353;
  8. int n;
  9. ll a[maxn],dp[maxn],P[maxn];
  11. int main(){
  12.     cin>>n;
  13.     for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
  14.     P[0]=1;
  15.     for(int i=1;i<=n;i++)P[i]=P[i-1]*2%mod;
  17.     dp[1]=a[1]*P[n-1]%mod;
  18.     for(int i=2;i<=n;i++){
  19.         dp[i]=((dp[i-1]-a[i-1]*P[n-i]%mod)%mod+mod)%mod;    
  20.         dp[i]=(dp[i]+a[i]*P[n-i]%mod)%mod;
  21.     }
  23.     ll ans=0;
  24.     for(int i=1;i<=n;i++)
  25.         ans=(ans+dp[i])%mod;    
  26.     cout<<ans<<'\n';
  27. }

cf168b：概率+背包dp，每件物品有获得概率p，有的物品会消耗掉一格体积，有的物品可以扩容，问得到l个物品并且都装下的概率

dp[i][j][l]表示前i个物品，得到j个，剩下容量为l的概率，转移方程：dp[i][j][k]=pi*dp[i-1][j-1][k-ai]+(1-pi)dp[i-1][j][k]

因为是无序的，所以背包偏移+200来保证第三维下标为正，注意要从当前状态推导到下一状态

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define N 205
  4. double dp[N][N][N<<1];
  5. int n,L,k,a[N];
  6. double p[N];
  7. int main(){
  8.     cin>>n>>L>>k;
  9.     for(int i=1;i<=n;i++)cin>>p[i],p[i]*=0.01;
  10.     for(int i=1;i<=n;i++)cin>>a[i];
  12.     dp[0][0][200+k]=1;
  13.     for(int i=1;i<=n;i++){ 
  14.         for(int j=0;j<=i;j++)
  15.             for(int l=0;l<=400;l++){
  16.                 dp[i][j][l]+=(1-p[i])*dp[i-1][j][l];//没赢 
  17.                 if(a[i]==-1){
  18.      //是奖品 
  19.                     if(l)dp[i][j+1][l-1]+=p[i]*dp[i-1][j][l];
  20.                 }
  21.                 else {
  22.      //是背包 
  23.                     dp[i][j+1][min(l+a[i],400)]+=p[i]*dp[i-1][j][l];
  24.                 }
  25.             }
  26.     }
  28.     double ans=0;
  29.     for(int j=L;j<=n;j++)
  30.         for(int l=200;l<=400;l++)
  31.             ans+=dp[n][j][l];
  32.     printf("%.10lf\n",ans);
  33. }

cf513C——细节题：枚举拍卖价格i，用长度为n的二进制位，1表示第j个人出价>=i

n个里起码选两个1 ，这时有两种情况 1：一个选择>i,剩下的选的=i的概率，2：都选i的概率

每种状态的12情况的概率叠加，i的所有状态概率叠加就是价格为i时的概率

ContractedBlock.gif ExpandedBlockStart.gif

  1. /*
  2. 枚举拍卖价格i
  3. 用长度为n的二进制位，1表示第j个人出价>=i,0反之
  4.     n个里起码选两个1 
  5.         1：一个选择>i,剩下的选的=i的概率 
  6.         2：都选i的概率
  7.     每种状态的12情况的概率叠加
  8. 所有状态概率叠加就是价格为i时的概率 
  9. */ 
  10. #include<bits/stdc++.h>
  11. using namespace std;
  12. #define N 10005
  13. int n,L[10],R[10];
  14. double ans[N]; 
  15. int count(int x){
  16.     int res=0;
  17.     for(int i=0;i<n;i++)
  18.         if(x>>i & 1)res++;
  19.     return res;
  20. }
  21. int main(){
  22.     cin>>n;
  23.     for(int i=0;i<n;i++)cin>>L[i]>>R[i];
  24.     for(int i=1;i<=10000;i++){
  25.         for(int S=0;S<(1<<n);S++)if(count(S)>=2){
  26.             double pp1=0; 
  27.             for(int j=0;j<n;j++)if(S>>j & 1){
  28.      //情况1，枚举第j个作为>i的选项 
  29.                 double p1=1;
  30.                 if(L[j]>i)p1=1;
  31.                 else if(R[j]<=i)p1=0;
  32.                 else if(R[j]>i && L[j]<=i)p1*=1.0*(R[j]-i)/(R[j]-L[j]+1);
  34.                 for(int k=0;k<n;k++)if(k!=j){
  35.                     if(S>>k & 1){
  36.                         if(R[k]<i || L[k]>i)p1=0;
  37.                         else p1*=1.0/(R[k]-L[k]+1);
  38.                     }
  39.                     else {
  40.                         if(L[k]>=i)p1=0;
  41.                         else if(R[k]<i)p1*=1;
  42.                         else if(L[k]<i && R[k]>=i)p1*=1.0*(i-L[k])/(R[k]-L[k]+1);
  43.                     }
  44.                 }
  46.                 pp1+=p1;
  47.             }
  49.             double p2=1;//情况2，都选i 
  50.             for(int j=0;j<n;j++){
  51.                 if(S>>j & 1){
  52.      //第j人等于i 
  53.                     if(L[j]>i || R[j]<i)p2=0;
  54.                     p2*=1.0/(R[j]-L[j]+1);
  55.                 }    
  56.                 else {
  57.      //第j人小于i 
  58.                     if(R[j]<i)p2*=1;
  59.                     else if(L[j]>=i)p2=0;
  60.                     else if(L[j]<i && R[j]>=i)p2*=1.0*(i-L[j])/(R[j]-L[j]+1);
  61.                 }
  62.             }
  64.             ans[i]+=pp1+p2;
  65.         }
  66.     }
  67.     double sum=0;
  68.     for(int i=1;i<=10000;i++)
  69.         sum+=ans[i]*i;
  70.     printf("%.10lf\n",sum);
  71. }

cf846F——期望线性性

由期望的线性可加性，每个ai的贡献可以单独计算，每个ai的贡献当且仅当其作为区间[L,R]第一个出现的值
设ai上一次出现的位置是L[ai], 那么ai有贡献的区间总共有2*(i-L[ai])*(n-i+1)-1
用序列自动机往前跳

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define N 1000005
  5. int n,a[N],L[N],pos[N];
  6. double ans; 
  7. int main(){
  8.     cin>>n;
  9.     for(int i=1;i<=n;i++)cin>>a[i];
  10.     for(int i=1;i<=n;i++){
  11.         L[i]=pos[a[i]];
  12.         pos[a[i]]=i;
  13.     }
  14.     for(int i=1;i<=n;i++)
  15.         if(L[i]==i) ans+=2*(n-i+1)-1;
  16.         else ans+=2ll*(i-L[i])*(n-i+1)-1;
  17.     ans/=1ll*n*n;
  18.     printf("%.10lf\n",ans); 
  19. }

cf109b——求概率转化为 统计所有合法情况个数/所有情况个数

  1. 先把所有lucky数打表，排序后存在数组里
  2. 一段区间内恰好有k个数，那么这k个数必定是连续的，我们枚举枚举这一段连续的的左右下标i,j可以得到两个取值区间
  3. 左边界 [v[i-1]+1,v[i]] 右边界[v[j],v[j+1]-1]，然后这两个边界再和[pl,pr],[vl,vr]求交，求有多少可能的取值
  4. 求出对于每个i,j的合法边界个数，然后统计求和就可以

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include<bits/stdc++.h>
  2. using namespace std; 
  3. #define ll long long 
  4. ll a[2005],cnt,pl,pr,vl,vr,k;
  5. void dfs(ll num){
  6.     if(num>=1e9)return;
  7.     if(num)a[++cnt]=num;
  8.     dfs(num*10+4);dfs(num*10+7);
  9. }
  10. ll jiao(ll L1,ll R1,ll L2,ll R2){
  11.       //求区间交的长度 
  12.     if(R1<L2 || R2<L1)return 0;//不相交
  13.     ll L=max(L1,L2),R=min(R1,R2);
  14.     return R-L+1; 
  15. }
  16. int main(){
  17.     dfs(0);
  18.     cin>>pl>>pr>>vl>>vr>>k;
  19.     sort(a+1,a+1+cnt);
  20.     a[cnt+1]=1e9;
  22.     ll ans=0;
  23.     for(int i=1;i+k-1<=cnt;i++){
  24.         int j=i+k-1;
  25.         ll tmp1=jiao(pl,pr,a[i-1]+1,a[i]);
  26.         ll tmp2=jiao(vl,vr,a[j],a[j+1]-1);
  27.         ll tmp3=jiao(vl,vr,a[i-1]+1,a[i]);
  28.         ll tmp4=jiao(pl,pr,a[j],a[j+1]-1);
  29.         if(k==1){
  30.      //特判处理 
  31.             ans+=tmp1*tmp2+tmp3*tmp4;
  32.             ll tmp5=jiao(pl,pr,a[i],a[i]); 
  33.             ll tmp6=jiao(vl,vr,a[i],a[i]);
  34.             if(tmp5 && tmp6)ans--;//(a[i],a[i]这种情况算了两次) 
  35.         }
  36.         else 
  37.             ans+=tmp1*tmp2+tmp3*tmp4;
  38.     } 
  39.     printf("%.10lf\n",1.0*ans/((pr-pl+1)*(vr-vl+1)));
  40. }

cf54C——求概率转化为 统计所有合法情况个数/所有情况个数

问题：n个数，每个数的取值范围是[Li,Ri], 那么 k%的数第一个数为1的概率是多少

思路：先求出每个数取到首位为1的概率，然后用背包dp[i][j]表示前i个数有j个首位为1的概率

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long 
  4. #define N 1005
  5. ll n,L[N],R[N],K,k;
  6. double p[N],dp[N][N];
  8. ll jiao(ll L1,ll R1,ll L2,ll R2){
  9. /*    cout<<R1-L2<<" ";
  10.     cout<<R2-L1<<"\n";
  11. */    if(R1<L2 || R2<L1) return 0;
  12.     ll L=max(L1,L2),R=min(R1,R2);
  13.     return R-L+1;
  14. }
  15. double calc(ll low,ll up){
  16.     ll sum=0;
  17.     for(ll p=1;p<=1e18;p*=10){
  18.         sum+=jiao(p,p*2-1,low,up);
  19.         if(p==1e18)break;
  20.     }
  21.     return 1.0*sum/(up-low+1);
  22. }
  24. int main(){
  25.     cin>>n;
  26.     for(int i=1;i<=n;i++){
  27.         cin>>L[i]>>R[i];
  28.         p[i]=calc(L[i],R[i]);
  29.     }
  30.     cin>>K;
  31.     k=(n*K)/100;
  32.     if(n*K%100!=0)    
  33.         k++;
  35.     dp[0][0]=1;
  36.     for(int i=1;i<=n;i++)
  37.         for(int j=0;j<=n;j++){
  38.             dp[i][j]+=(1-p[i])*dp[i-1][j];
  39.             if(j)
  40.                 dp[i][j]+=p[i]*dp[i-1][j-1];
  41.         }
  42.     double ans=0;
  43.     for(int i=k;i<=n;i++)
  44.         ans+=dp[n][i];
  45.     printf("%.10lf\n",ans);
  46. }

CF540D——概率递推dp(倒序dp或记忆化搜索)

用r个石头，s个剪刀，p个布，两个不同的相遇会减掉输的那个，相同的相遇则会不变
问最后只剩下石头，只剩下剪刀，只剩下布的概率
dp[i][j][k]表示剩下i个石头，j个剪刀，k个布的概率
因为本题初始状态是dp[r][s][p]=1，目标状态是dp[0][0][0],所以沿着这个状态从后往前推导就行
最后求出dp[1-r][0][0]就是石头的答案，其它同理

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define N 105
  4. int r,s,p;
  5. double dp[N][N][N];
  6. int main(){
  7.     cin>>r>>s>>p;
  8.     dp[r][s][p]=1;
  9.     for(int i=r;i>=0;i--)
  10.         for(int j=s;j>=0;j--)
  11.             for(int k=p;k>=0;k--){
  12.                 if(i==r && j==s && k==p)continue;
  13.                 int base=(i+j+k+1)*(i+j+k+1);
  14.                 if(i+1<=r && (j!=0||k!=0))dp[i][j][k]+=2.0*(i+1)*k/(base-(i+1)*(i+1)-j*j-k*k)*dp[i+1][j][k];
  15.                 if(j+1<=s && (i!=0||k!=0))dp[i][j][k]+=2.0*(j+1)*i/(base-i*i-(j+1)*(j+1)-k*k)*dp[i][j+1][k];
  16.                 if(k+1<=p && (i!=0||j!=0))dp[i][j][k]+=2.0*(k+1)*j/(base-i*i-j*j-(k+1)*(k+1))*dp[i][j][k+1];
  17.             } 
  18.     double ans1=0,ans2=0,ans3=0;
  19.     for(int i=1;i<=r;i++)ans1+=dp[i][0][0];
  20.     for(int j=1;j<=s;j++)ans2+=dp[0][j][0];
  21.     for(int k=1;k<=p;k++)ans3+=dp[0][0][k];
  22.     printf("%.10lf %.10lf %.10lf\n",ans1,ans2,ans3);
  23. }

cf351b——期望递推dp

给定一个初始排列{n},AB两个人轮流操作
A选择一个相邻的对交换位置
B 0.5概率随机交换一个相邻的逆序对，0.5几率随机交换一个相邻的顺序对，如果没有则不交换
当排列为递增排列时结束操作，A的策略是使两人操作次数最少，问期望操作次数
先统计逆序对cnt,然后每次要么减一个逆序对，要么加一个逆序对，然后再减一个逆序对
E[i]消i个逆序对的期望步数，因为AB两个操作分割后难以递推，那么直接一轮一轮绑定来算，
E[i]=0.5*(E[i-2]+2)+0.5*(E[i]+2)
E[0]=0,E[1]=1，求E[cnt]

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define N 3005
  4. int n,p[N];
  5. int C[N];
  6. void update(int x,int v){
  7.     while(x<=n){
  8.         C[x]+=v;
  9.         x+=x&-x;
  10.     }    
  11. }
  12. int query(int x){
  13.     int res=0;
  14.     while(x){
  15.         res+=C[x];
  16.         x-=x&-x;
  17.     }
  18.     return res;
  19. }
  20. double E[N*N];
  21. int main(){
  22.     cin>>n;
  23.     int cnt=0;
  24.     for(int i=1;i<=n;i++){
  25.         cin>>p[i];
  26.         cnt+=query(n)-query(p[i]);
  27.         update(p[i],1);
  28.     }
  29.     E[0]=0;E[1]=1;
  30.     for(int i=2;i<=cnt;i++)
  31.         E[i]=4+E[i-2];
  32.     printf("%lf\n",E[cnt]);
  33. }

cf235b——概率期望的性质，

n个点，第i个点有pi概率是1，对于一段连续的长度为len的1，得分为len*len,问这个序列的得分期望值

核心：把求连续段的期望 转化成求在这个连续段内任意点对(i,j)的贡献期望和+单点的贡献期望和

长度为len的段得分为len*len，考虑到平方，可以将其转化为统计点对
那么 len*len=2*C(len,2)+len
由这个等式右边第一项可以看出，长为len的连续段里每个点对(i,j)的贡献是2，这个点对出现的概率是mul{p[i]…p[j]}
原来要求的是len段的期望：len*len*其出现的概率，现在把这个段的期望拆成很多点对期望的和，(i,j)的期望就是2*mul{p[i]..p[j]}
右边第二项可以看出每个单点的贡献是1， 其出现概率就是pi

最后的结果是任意两个点对的期望和*2+单点期望和

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4. using namespace std;
  5. int const MAX = 1e5 + 5;
  6. double dp[MAX], p[MAX];
  8. int main()
  9. {
  10.     int n;
  11.     scanf("%d", &n);
  12.     double ans = 0;
  13.     for(int i = 1; i <= n; i++)
  14.     {
  15.         scanf("%lf", &p[i]);
  16.         ans += p[i];
  17.     }
  18.     for(int i = 2; i <= n; i++)
  19.     {
  20.         dp[i] = (dp[i - 1] + p[i - 1]) * p[i];
  21.         ans += 2 * dp[i];
  22.     }
  23.     printf("%.10f\n", ans);
  24. }

cf768D——标准二维概率dp

一开始想着按求期望那个套路来求，最后发现一个二维概率dp可以直接解决

有k种不同的球，每天随机得到一种颜色的球，问每种球至少得到一个的概率大于p的期望天数
dp[i][j]表示前i天得到j个不同的求的概率
dp[0][0]=1,dp[1][1]=1
dp[i][j]=j/k*dp[i-1][j]+(k-(j-1))/k*dp[i-1][j-1]
目标状态是dp[1..10000][k]
对于每个询问p，枚举i[1,10000],只要dp[i][k]>=p,就是答案

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define N 1005
  4. double p,dp[10005][N];
  5. int k,q; 
  6. int main(){
  7.     cin>>k>>q;
  8.     dp[0][0]=1;
  9.     for(int i=1;i<=10000;i++)
  10.         for(int j=1;j<=min(i,k);j++)
  11.             dp[i][j]=1.0*j/k*dp[i-1][j]+1.0*(k-(j-1))/k*dp[i-1][j-1];
  12.     while(q--){
  13.         cin>>p;
  14.         p/=2000;
  15.         for(int i=1;i<=10000;i++)
  16.             if(dp[i][k]>=p){
  17.                 cout<<i<<'\n';
  18.                 break;
  19.             }
  20.     }
  21. }

cf15E——状态压缩+概率dp

ContractedBlock.gif ExpandedBlockStart.gif

  1. /*
  2. dp[S]表示状态为S的概率
  3. dp[(1<<n)-1]=1,从大到小枚举S（或记忆化搜索），然后再枚举任意一个数位，来更新其他状态就可以
  4. 复杂度约为2^26 
  5. */
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8. int n;
  9. double dp[1<<18],a[20][20];
  10. int count(int S){
  11.     int res=0;
  12.     for(int i=0;i<n;i++)
  13.         if(S>>i & 1)res++;
  14.     return res;
  15. }
  16. int main(){
  17.     cin>>n;
  18.     for(int i=0;i<n;i++)
  19.         for(int j=0;j<n;j++)
  20.             cin>>a[i][j];
  22.     int mask=(1<<n)-1;
  23.     dp[mask]=1;
  25.     for(int S=mask;S;S--){
  26.         int cnt=count(S);
  27.         if(cnt<=1)continue;
  28.         cnt=cnt*(cnt-1)/2; 
  29.         for(int i=0;i<n;i++)if(S>>i & 1){
  30.             for(int j=i+1;j<n;j++)if(S>>j & 1){
  31.                 if(i==j)continue;
  32.                 dp[S-(1<<j)]+=a[i][j]*dp[S]/cnt;
  33.                 dp[S-(1<<i)]+=a[j][i]*dp[S]/cnt;
  34.             }
  35.         }
  36.     }
  38.     for(int i=0;i<n;i++)
  39.         printf("%.10lf ",dp[1<<i]);
  41.     return 0; 
  42. }

cf912d——优先队列贪心

  1. 在nm网格图上标记k个点，然后用r*r的矩阵随机覆盖网格图，得分是覆盖住的点的个数
  2. 现在求一种标记策略，使随机覆盖得分的期望最大
  3. 对于一种标记策略，随机覆盖的期望可以转化为每个点被覆盖的期望值之和
  4. 显然最中间的点的被覆盖期望最大，然后是其四周，依次类推
  5. 用优先队列来维护，每次弹出一个元素，加入其周围四个元素，取前k个

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include<bits/stdc++.h>
  2. #include<queue>
  3. using namespace std;
  4. #define N 100005
  5. #define ll long long
  6. struct Node{
  7.     ll x,y;
  8.     double e;
  9.     Node(){}
  10.     Node(ll x,ll y,double e):x(x),y(y),e(e){}
  11. };
  12. bool operator<(Node a,Node b){
  13.     return a.e<b.e;
  14. }
  15. priority_queue<Node>pq;
  16. map<pair<ll,ll> ,int>vis;
  17. double ans;
  19. ll n,m,r,k;
  20. double calc(ll x,ll y){
  21.     ll up=max(1ll,x-r+1),down=min(n-r+1,x);
  22.     ll left=max(1ll,y-r+1),right=min(m-r+1,y);
  23.     return 1.0*(down-up+1)*(right-left+1)/(n-r+1)/(m-r+1);
  24. }
  26. int a[4]={-1,1,0,0},b[4]={
  27.      0,0,1,-1};
  29. int main(){
  30.     cin>>n>>m>>r>>k;
  31.     Node s;
  32.     s.x=r;s.y=r;
  33.     s.e=calc(s.x,s.y);
  34.     pq.push(s);
  36.     while(pq.size() && k){
  37.         Node c=pq.top();pq.pop();
  38.         ll x=c.x,y=c.y;
  39.         if(vis[make_pair(x,y)]==1)continue;
  40.         vis[make_pair(x,y)]=1;
  41.         k--;ans+=c.e;
  43.         for(int i=0;i<4;i++){
  44.             ll dx=x+a[i],dy=y+b[i];
  45.             if(dx<1 || dy<1 || dx>n || dy>m)continue;
  46.             Node t;
  47.             t.x=dx,t.y=dy;
  48.             t.e=calc(dx,dy);
  49.             pq.push(t);
  50.         }
  51.     }
  53.     printf("%.10lf\n",ans);
  54. }

cf452C——组合数学概率推导

一副牌n张牌，把m副牌混在一起，再抽出n张，有放回地抽取两张，问一样的概率
当只有一副牌时，抽到和原来一样的概率是1/n
当有m副牌时，分成两部分考虑
　　第一部分：第二次抽的是第一次抽的那张牌，概率是1/n
　　第二部分，第二次抽的不是第一次抽的那张牌，但是和第一次抽的相同，概率是(n-1)/n*(n-1)/(n*m-1)
为什么要分阶段考虑：因为两次洗牌时的洗牌范围不同，所以需要对每个范围求一次概率
　　先在n*m张牌里取一张牌，然后放到范围n里洗牌，那么下一次还取到这张牌的概率是1/n，不取到这张牌的概率是(n-1)/n
　　从其他n-1张牌里取出和这张牌相同的概率是(n-1)/(n*m-1)

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. int main()
  5. { 
  6.     double n,m;
  7.     cin>>n>>m;
  8.     if (n==1&&m==1){printf("1\n");return 0;}
  9.     double a=1.0/n;
  10.     double b=(n-1)*(m-1)/n/(n*m-1);
  11.     printf("%.7lf\n",a+b);
  13. }

cf261b ——组合数学+dp，期望=总量/总方案数

  1. 给定一个序列ai表示第i个人的体积，现在这n个人随机排列，依次进入体积为n的房间里，问房间里人数的期望
  2. 原问题转化成 总方案数/全排列
  3. 假定第一个无法进入的人是x，那么进入餐厅的人体积可以是区间[p-a[x]+1,p]
  4. 令dp[i,j,k]表示前i个人，进了j个，体积是k的方案数
  5. dp[0][0][0]=1,
  6. dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-a[i]]
  7. 最后要求的是每个 j*j!*(n-j-1)!*dp[n][j][p-a[x]+1,p]，即j*进入j个人的方案数，然后求和就是总方案数

ContractedBlock.gif ExpandedBlockStart.gif

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define N 55
  4. int n,a[N],p;
  5. double dp[N][N][N],F[N];
  7. int main(){
  8.     F[0]=1;
  9.     for(int i=1;i<=50;i++)F[i]=1.0*i*F[i-1];
  11.     cin>>n;int sum=0;
  12.     for(int i=1;i<=n;i++)
  13.         cin>>a[i],sum+=a[i];
  14.     cin>>p;
  15.     if(sum<=p){cout<<n<<endl;return 0;}
  17.     double ans=0;
  18.     for(int x=1;x<=n;x++){
  19.         memset(dp,0,sizeof dp);
  20.         dp[0][0][0]=1;
  21.         for(int i=1;i<=n;i++)
  22.             for(int j=0;j<=i;j++)
  23.                 for(int k=0;k<=p;k++){
  24.                     if(x==i){dp[i][j][k]=dp[i-1][j][k];continue;}
  25.                     dp[i][j][k]=dp[i-1][j][k];
  26.                     if(j && k>=a[i])dp[i][j][k]+=dp[i-1][j-1][k-a[i]];
  27.                 }
  28.         for(int j=1;j<n;j++)
  29.             for(int k=max(0,p-a[x]+1);k<=p;k++)
  30.                 ans+=F[j]*F[n-j-1]*j*dp[n][j][k];
  31.     }    
  32.     printf("%.10lf\n",ans/F[n]);
  33. }

转载于:https://www.cnblogs.com/zsben991126/p/11446533.html

发表评论

表情：
评论列表 （有 0 条评论，151人围观）

还没有评论，来说两句吧...

相关阅读

    相关 cf期望概率专题

    cf1009E：求到第i段期望和的比较困难，但是单独求每段的期望是比较容易的，所以单独对每段求和，然后累计总和 E\[i\]=1/2\a1+1/4\a2+...+1/2^(i

    傷城~傷城~/ 0 赞/ 152 阅读