思路

• 定义动态规划：令 $f_i$ 表示在第 $i$ 周开始且当前不被禁赛时，从第 $i$ 周到赛季结束的最大期望。

• 决策：

  • 参加第 $i$ 场：得到期望 $p_i$，并且以 $1-q_i$ 进入状态 $f_{i+1}$，以 $q_i$ 被禁赛而跳到 $f_{i+2}$。
  • 跳过第 $i$ 场：保持不被禁赛，进入 $f_{i+1}$。

• 转移

$f_i$=$\max$($p_i$+$(1-q_i)$,$f_{i+1}$+$q_i$,$f_{i+2}$,$f_{i+1}$)

题目内容

铁制品工艺练习赛(Iron Craft Practising Contest，ICPC)赛季即将开始。在接下来的连续 $n$ 周内，每周将在某个城市举行一次比赛。

根据经验，小C在第 $i$ 场比赛中成功打铁的概率为 $p_i$ 。

如果小C参加比赛，则在赛后有 $q_i$ 的概率被教练禁止参加下一周（即第 $i+1$ 周）的比赛。无论他是否参加第 $i+1$ 周的比赛，此禁令都会在第 $i+1$ 周结束后自动解除。

小C可以选择任意场比赛参加。小C希望最大化本赛季打铁次数的期望值。

【名词解释】

期望值：期望值是概率论中的一个概念，指随机变量在多次试验中的平均结果。例如，投掷一枚均匀硬币，正面向上得分 $1$ ，反面向上得分 $0$ ，其期望值为 $0.5$ 。

输入描述

第一行输入一个整数 $n (1≤n≤10^6)$，表示比赛场次数。

接下来 $n$ 行，每行输入两个实数 $p_i,q_i (0≤p_i,q_i≤1)$，其中：

• $p_i$ 表示第 $i$ 场比赛成功打铁的概率；
• $q_i$ 表示第 $i$ 场比赛后被禁止参加下一场比赛的概率。

输出描述

输出一个实数，表示小C本赛季打铁次数的最大期望值。

由于浮点数计算可能产生误差，当误差的量级不超过 $10^{−6}$ 时，答案将被接受。

具体来说，设你的答案为 $a$，标准答案为 $b$ ，当且仅当

$\frac{∣a−b∣}{max⁡(1,∣b∣)}≤10^{−6}$ 时，答案被接受。

样例1

输入

2
0.5 0.5
0.5 0.0

输出

0.75

说明

• 第 $1$ 场比赛：成功概率 $0.5$ ，禁赛概率 $0.5$。

• 在第 $1$ 场之后，有 $0.5$ 的概率被禁赛，此时无法参加第 $2$ 场；有 $0.5$ 的概率可继续参加。

• 如果继续参加，则在第 $2$ 场比赛中成功概率为 $0.5$ 。

• 因此期望值为 $0.5+0.5×0.5=0.75$ 。

样例2

输入

5
1.0 0.0
1.0 0.0
1.0 0.0
1.0 0.0
1.0 0.0

输出

5.0

说明

在该样例中，每场比赛都必定成功且不会被禁赛，因此总期望打铁次数为 $5$ 。