天津市免费建站,做网站好还是小程序好,北京网站设计的公司,网站前端开发培训西安problem
有 nnn 个随机数生成器#xff0c;第 iii 个生成器可以均匀随机地生成 [Li,Ri][L_i,R_i][Li,Ri] 内的一个实数。
现在你要玩个游戏#xff0c;从第 111 个生成器到第 nnn 个生成器#xff0c;每次当前生成器会生成一个数#xff0c;你需要选择#xff1a;
…problem
有 nnn 个随机数生成器第 iii 个生成器可以均匀随机地生成 [Li,Ri][L_i,R_i][Li,Ri] 内的一个实数。
现在你要玩个游戏从第 111 个生成器到第 nnn 个生成器每次当前生成器会生成一个数你需要选择
相信鲁迅拿走这个数游戏结束。相信鲁迅放弃这个数和这个生成器使用下一个生成器前提是下一个生成器必须存在。
求使用使得期望答案最大的策略时期望答案是多少。
solution
observation对于一个均匀随机生成 [Li,Ri][L_i,R_i][Li,Ri] 的生成器生成数的期望为 LiRi2\frac{L_iR_i}{2}2LiRi。
显然如果上一个生成器产生的期望为 xxx下一个生成器产生数的期望 yyy且 xyxyxy肯定是选择下一个生成器。
更一般地从后往前推。
设 fi:f_i:fi: 从第 iii 个生成器开始游戏得到的最大期望。
比较与 Li−1,Ri−1L_{i-1},R_{i-1}Li−1,Ri−1 的大小关系。
fiRi−1f_{i}R_{i-1}fiRi−1则 fi−1fif_{i-1}f_{i}fi−1fifiLi−1f_{i}L_{i-1}fiLi−1则 fi−1Li−1Ri−12f_{i-1}\frac{L_{i-1}R_{i-1}}{2}fi−12Li−1Ri−1otherwise\text{otherwise}otherwisekfi−Li−1Ri−1−Li−1⇒fi−1k∗fi(1−k)∗(fiRi−1)2k\frac{f_{i}-L_{i-1}}{R_{i-1}-L_{i-1}}\Rightarrow f_{i-1}k*f_{i}(1-k)*\frac{(f_iR_{i-1})}{2}kRi−1−Li−1fi−Li−1⇒fi−1k∗fi(1−k)∗2(fiRi−1)
计算方法就是加权平均。
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;
}
