题意概述

给定长度为 $n$ 的数组 $A$,数组 $B$ 为 $A$ 的前缀和数组,保证 $B_n = 0$。

现在可以重复地从 $A$ 中选择一些数,它们的编号排成数列 $P_1, P_2, P_3, …, P_k, P_{k+1}$,它满足以下两个条件:

  1. $P_1=P_{k+1}$;

  2. 存在一个 $2 \le i \le k$,使得对于任意 $j < i$, 都满足 $B_{P_j} \le B_{P_{j+1}}$;而对于任意 $k \ge j \ge i$, 都满足 $B_{P_j} \ge B_{P_{j+1}}$。

现在定义数列 $P$ 带来的收益。对于 $P$ 中每对相邻元素 $i,j$,它们对收益的贡献为 $\dfrac{(A_i – A_j) B_i B_j}{2A_iA_j}$。

求最大收益。

思路

我们观察贡献的式子,发现可以分解成 $\dfrac{1}{2} \times (\dfrac{B_j}{A_j}\cdot B_i – \dfrac{B_i}{A_i}\cdot B_j)$。也就是说,我们将原来的 $A,B$ 数组转化成二维平面上 $n$ 个点,第 $i$ 个点坐标为 $(B_i,\dfrac{B_i}{A_i})$,那么 $i$ 到 $j$ 产生的贡献就是这两个点与原点构成的有向三角形面积。结合 $P$ 数组的限制以及 $B_n=0$ 这两个条件,我们确定我们要找的只是一个凸包而已,它的面积就是答案。

代码

  1. 【笔记】平面凸包的计算 – XG Zepto's
    Dec 04, 2018

    […] 【正睿 OI 2019 省选】终 / 题解 […]

    Reply