点击刷新
题意
给定\(n,g,t\)及序列\(\{c_i：1\le i\le n\}\)
有\(n\)张桌子，每张可容纳的人数为\(c_i\)
有\(t\)群人来吃饭，每群人数为\([1,g]\)中随机的一个整数\(x\)，会选一张最小的能容纳\(x\)个人的桌子坐下（若没有则离开）
求最后的期望人数
\(n,t\le 100\)，\(g,c_i\le 200\)
做法
假设\(c_1\le c_2\le \cdots\le c_n\le g\)
考虑观察题目的性质：
- 最后就坐的桌子，是若干段连续的区间
- 若目前的一群人\(x\)人就坐，之前\(\le x\)的人数的群体一定也就坐了
令\(f_{l,r}\)为前\(r-l+1\)群人，恰好就坐\([l,r]\)的概率，枚举最后一群人就坐的位置，转移显然：
\[\begin{cases}
f_{i,i-1}=1\\
f_{l,r}=\sum\limits_{k=l}^{r} \frac{c_k-c_{l-1}}{g}{r-l\choose r-k}f_{l,k-1}f_{k+1,r}
\end{cases}\]
令\(g_{i,j}\)为前\(j\)群人，在\([1,i)\)就坐的概率
转移利用\(f\)，枚举与\(i-1\)在一段的数量（可能为\(0\)），转移显然：
\[\begin{cases}
g_{0,0}=1\\
g_{i,j}=\sum\limits_{len=0}^j {j\choose len}f_{i-len,i-1}\cdot g_{i-len-1,j-len}
\end{cases}\]
根据期望的线性性，计算每一张桌子\(i\)的贡献：
\[\sum\limits_{k=1}^{min(i,t)} \sum\limits_{j=1,i-j+1\le k}^i (\frac{1}{g}\sum\limits_{x=c_{j-1}+1}^{c_i}x)f_{j,i-1}\cdot g_{j-1,k-(i-j+1)}\sum\limits_{num=k}^{t}{t\choose num}{k-1\choose i-j}(1-\frac{c_i}{g})^{t-num}(\frac{c_i}{g})^{num-k}
\]
枚举在第\(i\)张桌子就坐后的这一刻，\([1,i]\)有\(k\)张桌子已经有人
枚举就坐后的这一刻，\(i\)这一极长段是以\(j\)开始的
枚举总共有\(num\)个\(\le c_i\)的人群
这样做单次是\(O(n^3)\)的，观察最后那个\(\sum\)，稍加变形就很容易做到单次\(O(n^2)\)了：
\[\begin{aligned}
{k-1\choose i-j}(\frac{c_i}{g})^{-k}\sum\limits_{num=k}^{t}{t\choose num}(1-\frac{c_i}{g})^{t-num}(\frac{c_i}{g})^{num}\\
\end{aligned}\]
总复杂度\(O(n^3)\)，但实测\(O(n^4)\)跑得飞快
© 著作权归作者所有
举报
发表评论
0/200
