problem

有 $n$ 個隨機數生成器，第 $i$ 個生成器可以均勻隨機地生成 $[L_i,R_i]$ 內的一個實數。

現在你要玩個游戲，從第 $1$ 個生成器到第 $n$ 個生成器，每次當前生成器會生成一個數，你需要選擇：

相信魯迅，拿走這個數，游戲結束。

相信魯迅，放棄這個數和這個生成器，使用下一個生成器（前提是下一個生成器必須存在）。

求使用使得期望答案最大的策略時，期望答案是多少。

solution

observation：對于一個均勻隨機生成 $[L_i,R_i]$ 的生成器，生成數的期望為 $\frac{L_i+R_i}{2}$。

顯然，如果上一個生成器產生的期望為 $x$，下一個生成器產生數的期望 $y$，且 $x<y$，肯定是選擇下一個生成器。

更一般地，從后往前推。

設 $f_i:$ 從第 $i$ 個生成器開始游戲得到的最大期望。

比較與 $L_{i?1},R_{i?1}$ 的大小關系。

• $f_i>R_{i?1}$，則 $f_{i?1}=f_i$
• $f_i<L_{i?1}$，則 $f_{i?1}=\frac{L_{i?1}+R_{i?1}}{2}$
• $\text{otherwise}$，$k=\frac{f_i?L_{i?1}}{R_{i?1}?L_{i?1}}?f_{i?1}=k?f_i+(1?k)?\frac{(f_i+R_{i?1})}{2}$

計算方法就是加權平均。

code

#include <cstdio> #include <iostream> using namespace std; #define double long double #define maxn 1000005 #define eps 1e-7 int n; double l[maxn], r[maxn], f[maxn];int main() {freopen( "pag.in", "r", stdin );freopen( "pag.out", "w", stdout );scanf( "%d", &n );for( int i = 1;i <= n;i ++ ) scanf( "%Lf %Lf", &l[i], &r[i] );f[n] = ( l[n] + r[n] ) / 2;for( int i = n - 1;i;i -- ) {if( f[i + 1] - r[i] >= eps ) f[i] = f[i + 1];else if( f[i + 1] - l[i] >= eps ) {double k = ( f[i + 1] - l[i] ) / ( r[i] - l[i] );f[i] = k * f[i + 1] + ( 1 - k ) * ( r[i] + f[i + 1] ) / 2;}else f[i] = ( l[i] + r[i] ) / 2;}double ans = 0;for( int i = 1;i <= n;i ++ ) ans = max( ans, f[i] );printf( "%.5Lf\n", ans );return 0; }

總結

以上是生活随笔為你收集整理的聚烷撑乙二醇（数学+期望）的全部內容，希望文章能夠幫你解決所遇到的問題。

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