题目链接:LOJ 2483
有 $n$ 根柱子依次排列,每根柱子都有一个高度。第 $i$ 根柱子的高度为 $h_i$。
现在想要建造若干座桥,如果一座桥架在第 $i$ 根柱子和第 $j$ 根柱子之间,那么需要 $(h_i - h_j)^2$ 的代价。
在造桥前,所有用不到的柱子都会被拆除,因为他们会干扰造桥进程。第 $i$ 根柱子被拆除的代价为 $w_i$,注意 $w_i$ 不一定非负,因为可能政府希望拆除某些柱子。
现在政府想要知道,通过桥梁把第 $1$ 根柱子和第 $n$ 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。
数据范围:$2 \le n \le 10 ^ 5$,$0 \le h_i, \vert w_i \vert \le 10 ^ 6$。
题目链接:LOJ 2353
小 Y 最近在一家金券交易所工作。该金券交易所只发行交易两种金券:$A$ 纪念券(以下简称 $A$ 券)和 $B$ 纪念券(以下简称 $B$ 券)。每个持有金券的顾客都有一个自己的帐户。金券的数目可以是一个实数。每天随着市场的起伏波动,两种金券都有自己当时的价值,即每一单位金券当天可以兑换的人民币数目。我们记录第 $i$ 天中 $A$ 券和 $B$ 券的价值分别为 $A_i$ 和 $B_i$(元 / 单位金券)。为了方便顾客,金券交易所提供了一种非常方便的交易方式:比例交易法。比例交易法分为两个方面:
注意:同一天内可以进行多次操作。
小 Y 是一个很有经济头脑的员工,通过较长时间的运作和行情测算,他已经知道了未来 $n$ 天内的 $A$ 券和 $B$ 券的价值 $A_i,B_i$ 以及 $Rate_i$。他还希望能够计算出来,如果开始时拥有 $S$ 元钱,那么 $n$ 天后最多能够获得多少元钱。
数据范围:$1 \le n \le 10 ^ 5$,$0 < A_i, B_i \le 10$,$0 < Rate_i \le 100$,$0 \le \text{答案}\le 10 ^ 9$。