很喵的一道題（我可不是因為看了YOUSIKI的題解才變成這樣的）

$ans=\sum_{x<=n}\sum_{i<=n} iP(L=i)$ 其中P(x)表示視線為x的概率。

所以只需要求出對于每個人的$\sum_{i<=n} iP(L=i)$就可以了。

然后我們轉化$\sum_{i<=n}P(L>=i)$ 這步很喵，大概運用的差分的思想。

然后我們大力展開之后合并，就可以得到一堆組合數，然后考慮組合數的意義，對組合數合并，最后得出$ans=\frac{n+1}{k+2}$k表示不小于每個人的人的個數。

然后就是$\Theta(n)$統計即可

#include <map> #include <ctime> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define F(i,j,k) for (int i=j;i<=k;++i) #define D(i,j,k) for (int i=j;i>=k;--i)int n,cnt[1005],sum; double ans; int main() {scanf("%d",&n); n++;for (int i=1,j;i<n;++i) scanf("%d",&j),cnt[j]++;for (int i=1;i<=1000;++i) ans+=1.0*cnt[i]*n/(n-sum),sum+=cnt[i];printf("%.2lf\n",ans); }

　　

轉載于:https://www.cnblogs.com/SfailSth/p/6669732.html

總結

以上是生活随笔為你收集整理的BZOJ 2720 [Violet 5]列队春游 ——期望DP的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。