主要是因为，在洛谷大部分题解都是写李超线段树优化的，看到标签我也被诈骗了，推完式子才发现具有单调的良好性质。遂写一篇典型的斜率优化 dp 的题解。
题意
第 i i i 号岛屿有 t i t_{i} ti 人，但是你很挑剔，每次你从 j j j 号岛屿到达 i i i 号岛屿时，你只会在到达的岛屿上做 t i × t j t_{i} \times t_{j} ti×tj 件好事（一件好事可以获得 1 1 1 点 R P \mathrm{RP} RP )。
唯一不足的是，由于你在岛上住宿，劳民伤财，你会扣除巨量 RP，第 i i i 号岛屿的住宿扣除 x i x_{i} xi 点 R P \mathrm{RP} RP。
注意: 将离开一个岛屿时，先将 R P \mathrm{RP} RP 扣除一半，再扣除住宿的 R P \mathrm{RP} RP，最后在新到达的岛屿上做好事，增加 R P \mathrm{RP} RP。离开 1 1 1 号岛屿时需要扣除在 1 1 1 号岛屿住宿的 R P \mathrm{RP} RP，当到达这段旅程的最后一个岛屿上时，要做完好事，行程才能结束，也就是说不用扣除在最后到达的岛屿上住宿的 R P \mathrm{RP} RP 。
你因为热爱旅行（RP），所以从 1 1 1 号岛屿开始旅行，初始时你有 0 0 0 点 R P \mathrm{RP} RP。你希望选择一些岛屿经过，最终选择一个岛屿停下来，求最大的 R P \mathrm{RP} RP 值是多少?
1 ≤ n ≤ 5 × 1 0 5 , 1 ≤ t i ≤ 20000 , 1 ≤ x i ≤ 2 × 1 0 8 1 \leq n \leq 5\times10^5,1 \leq t_{i} \leq 20000,1 \leq x_{i} \leq 2\times 10^8 1≤n≤5×105,1≤ti≤20000,1≤xi≤2×108。给定的 t i t_{i} ti 已经按照升序排序。
思路
考虑朴素的 dp，设 f i f_i fi 表示走到了第 i i i 个岛屿最大 R P \mathrm{RP} RP，注意到只能从小的岛屿转移到大的岛屿，于是就变成了一道典型的斜率式子题。
有：
f i = min j = 1 i { ⌊ f j 2 ⌋ − x j + t i t j } f_i=\min_{j=1}^{i}\left\{\left \lfloor \frac{f_j}{2} \right \rfloor-x_j+t_it_j\right\} fi=j=1mini{⌊2fj⌋−xj+titj}
设 j 1 < j 2 j1<j2 j1<j2 且 j 2 j2 j2 优于 j 1 j1 j1，那么：
⌊ f j 1 2 ⌋ − x j 1 + t i t j 1 < ⌊ f j 2 2 ⌋ − x j 2 + t i t j 2 \left \lfloor \frac{f_{j1}}{2} \right \rfloor-x_{j1}+t_it_{j1}<\left \lfloor \frac{f_{j2}}{2} \right \rfloor-x_{j2}+t_it_{j2} ⌊2fj1⌋−xj1+titj1<⌊2fj2⌋−xj2+titj2
⌊ f j 1 2 ⌋ − ⌊ f j 2 2 ⌋ − x j 1 + x j 2 < t i ( t j 2 − t j 1 ) \left \lfloor\frac{f_{j1}}{2}\right\rfloor-\left\lfloor\frac{f_{j2}}{2}\right\rfloor-x_{j1}+x_{j2}<t_i(t_{j2}-t_{j1}) ⌊2fj1⌋−⌊2fj2⌋−xj1+xj2<ti(tj2−tj1)
注意到可能有 t j 2 − t j 1 = 0 t_{j2}-t_{j1}=0 tj2−tj1=0（这为下文我的出锅埋下伏笔），根据上一篇题解的经验，我们拆分斜率的分子分母。实则 t j 2 − t j 1 ≥ 0 t_{j2}-t{j1}\ge0 tj2−tj1≥0
⌊ f j 1 2 ⌋ − ⌊ f j 2 2 ⌋ − x j 1 + x j 2 ( t j 2 − t j 1 ) < t i \frac{\left \lfloor\frac{f_{j1}}{2}\right\rfloor-\left\lfloor\frac{f_{j2}}{2}\right\rfloor-x_{j1}+x_{j2}}{(t_{j2}-t_{j1})}<t_i (tj2−tj1)⌊2fj1⌋−⌊2fj2⌋−xj1+xj2<ti
s l o p e < t i slope<t_i slope<ti 且 t i t_i ti 单调递增，和玩具装箱是同一种类型，维护单调递增斜率，最优决策取队首。
弹出决策点时，一定要记得写成小于等于的形式，对我这种写习惯了小于的人很不友好pwq，害得我虚空调试了半个小时。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dd double
const ll N=5e5+9,inf=0x7f7f7f7f;
ll n,t[N],x[N];
ll f[N],q[N];
ll slope_up(ll j1,ll j2)
{return f[j1]/2-f[j2]/2-x[j1]+x[j2];
}
ll slope_down(ll j1,ll j2)
{return t[j2]-t[j1];
}
int main()
{scanf("%lld",&n);for(int i=1;i<=n;i++)scanf("%lld",&t[i]);for(int i=1;i<=n;i++)scanf("%lld",&x[i]);ll hh=0,tt=0;q[0]=1;ll ans=-inf;for(int i=2;i<=n;i++){while(hh<tt&&slope_up(q[hh],q[hh+1])<t[i]*slope_down(q[hh],q[hh+1]))hh++;f[i]=f[q[hh]]/2-x[q[hh]]+t[i]*t[q[hh]];while(hh<tt&&slope_up(q[tt],i)*slope_down(q[tt-1],q[tt])<=slope_up(q[tt-1],q[tt])*slope_down(q[tt],i))tt--;q[++tt]=i;}for(int i=1;i<=n;i++)ans=max(ans,f[i]);cout<<ans;return 0;
}
