列队春游 BZOJ 2720

zJx_Lm · 2021-05-22 17:06:34 · 个人记录

组合数学 & 概率dp

1. 设 num[i] 为身高为i的小朋友的总数 ；f[i] 为 1位 身高为i的小朋友贡献的期望值；
2. 则 ans=sum( num[i]*f[i] ) [ 0<=i<=1000 && num[i]!=0 ]

那么问题就转化为求 f[i] 的值。

• 设 s 为身高 ( j ) 小于 身高 (i) 的 集合，

• 则 d[j] ( j 对（i的期望）做的贡献 ) [ j 属于 s ]

  == (d[j]的排列数)/（总排列数）

• f[i] = （ num (s) * d[j] +1.0 ) 【i前有x个小朋友，贡献的视野为x+1，所以 “+1.0” 】

d[j]的排列数 ？？？？

首先将【除j外的集合s】 去掉，还剩n-s+1个小朋友， j恰好在在i前面的方案数为 :

(n-s)! 【将i与j捆在一起，还剩n-s个个体，所以为 (n-s)! 】

然后安排那 s-1 个被抛弃的小朋友 方案数为 ：

A(n,s-1) 【s-1进n】

二者相乘 d[j] 的排列数为 (n-s)！ * A(n,s-1) == n！ / (n-s+1)

所以 d[j] == n！/ (n-s+1) / n！== 1/(n-s+1) ;

f[i]=( num(s)* d[j]+1.0 ）;

代码实现 ：

CODE

#include <cstdio>
#define db double
#define re register
#define max(x,y) x>y? x:y
using namespace std;
const int maxn=1010;
int n,h,s,maxh,num[maxn];
signed main(void) {
    scanf("%d",&n);
    for(re int i=1;i<=n;i++) {
        scanf("%d",&h);
        maxh=max(maxh,h);
        num[h]++;
    }
    double ans=0;
    for(re int i=1;i<=maxh;i++) if(num[i]) {
        ans+=(db)num[i]*(db)(((db)s/(db)(n-s+1))+1.0);
        s+=num[i];
    }
    printf("%.2lf",ans);
}

我们搜索身高，顺便可以更新小于身高的总和 ；

// ZJX_LM //