4944.最优二叉搜索树

## 题目描述

最优二叉搜索树（$Optimal Binary Search Tree$）是通过从 $n$ 个实际键和$ n+1 $个虚拟键构建二叉搜索树，以最小化搜索操作的期望成本。

给定一个按升序排列的键序列 $K = k_1, k_2, ..., k_n（k_1 < k_2 < ... < k_n）$，我们需要构建一棵二叉搜索树。对于每个键$ k_i$，其被搜索的概率为$ p_i$。此外，还存在$ n+1$ 个虚拟键 $d_0, d_1, d_2, ..., d_n$，表示不在 $K$ 中的值。这些虚拟键的定义如下：

- 若 $i = 0$，则 $d_0 $表示所有小于$ k_1 $的值；

- 若 $i = n$，则$ d_n $表示所有大于$ k_n $的值；

- 若 $1 \le i \le n-1$，则 $d_i $表示所有介于$ k_i $和$ k_{i+1}$ 之间的值。

对于每个虚拟键 $d_i$，其被搜索的概率为 $q_i$。所有概率满足以下条件：

实际键概率之和 $+$ 虚拟键概率之和 $= 1$，即

$\sum_{i=1}^{n}p_i$+$\sum_{i=0}^{n}q_i$=1

在二叉搜索树 $T $中，一次搜索的期望成本为：

E_T= $\sum_{i=1}^{n}(depth_T(k_i)+1)\cdotp_i$+ $\sum_{i=0}^{n}(depth_T(d_i)+1)\cdotq_i$，

其中 $depth_T(v) $表示节点 $v $在树 $T $中的深度。我们的目标是针对给定的概率集合，构造一棵期望搜索成本最小的二叉搜索树，称为最优二叉搜索树。

在实际树结构中，每个键$ k_i $是内部节点，而每个虚拟键$ d_i $是叶节点。例如，下图展示了根据输入样例构造的最优二叉搜索树。

### 目标任务

编写一个程序，计算在给定$ p_i$（表示搜索关键字$ k_i $的概率）和 $q_i$（表示搜索虚拟键$ d_i $的概率）的情况下，最优二叉搜索树（$Optimal BST$）的搜索操作期望值。

## 输入格式

第一行给定一个整数$n$，表示关键字的数量。

第二行给定$p_i（1 \le i \le n）$，以四位小数的实数形式给出。

第三行给定 $q_i（0 \le i \le n）$，以四位小数的实数形式给出。

## 输出格式

在一行中输出最优二叉搜索树搜索操作的期望值。输出结果的误差不得超过10⁻⁴。

## 数据范围

- $1\len\le500$
- $0<p_i,q_i<1$
- $\sum_{i=1}^{n}p_i$+$\sum_{i=0}^{n}q_i$=1

## 输入
```in1
5
0.1500 0.1000 0.0500 0.1000 0.2000
0.0500 0.1000 0.0500 0.0500 0.0500 0.1000
```

## 输出
```out1
2.75000000
```

```in2
7
0.0400 0.0600 0.0800 0.0200 0.1000 0.1200 0.1400
0.0600 0.0600 0.0600 0.0600 0.0500 0.0500 0.0500 0.0500
```

```out2
3.12000000
```