主要是因为，在洛谷大部分题解都是写李超线段树优化的，看到标签我也被诈骗了，推完式子才发现具有单调的良好性质。遂写一篇典型的斜率优化 dp 的题解。

题意

第 $i$ 号岛屿有 $t_i$ 人，但是你很挑剔，每次你从 $j$ 号岛屿到达 $i$ 号岛屿时，你只会在到达的岛屿上做 $t_i\times t_j$ 件好事（一件好事可以获得 $1$ 点 $\mathrm{RP}$ )。

唯一不足的是，由于你在岛上住宿，劳民伤财，你会扣除巨量 RP，第 $i$ 号岛屿的住宿扣除 $x_i$ 点 $\mathrm{RP}$。

注意: 将离开一个岛屿时，先将 $\mathrm{RP}$ 扣除一半，再扣除住宿的 $\mathrm{RP}$，最后在新到达的岛屿上做好事，增加 $\mathrm{RP}$。离开 $1$ 号岛屿时需要扣除在 $1$ 号岛屿住宿的 $\mathrm{RP}$，当到达这段旅程的最后一个岛屿上时，要做完好事，行程才能结束，也就是说不用扣除在最后到达的岛屿上住宿的 $\mathrm{RP}$ 。

你因为热爱旅行（RP），所以从 $1$ 号岛屿开始旅行，初始时你有 $0$ 点 $\mathrm{RP}$。你希望选择一些岛屿经过，最终选择一个岛屿停下来，求最大的 $\mathrm{RP}$ 值是多少?

$1\le n\le 5\times 10^5,1\le t_i\le 20000,1\le x_i\le 2\times 10^8$。给定的 $t_i$ 已经按照升序排序。

思路

考虑朴素的 dp，设 $f_i$ 表示走到了第 $i$ 个岛屿最大 $\mathrm{RP}$，注意到只能从小的岛屿转移到大的岛屿，于是就变成了一道典型的斜率式子题。

有：
$$f_i=\underset{j=1}{\overset{i}{\min }}\left\{\lfloor \frac{f_j}{2}\rfloor -x_j+t_i{t}_j\right\}$$

设 $j1<j2$ 且 $j2$ 优于 $j1$，那么：
$$\lfloor \frac{f_{j1}}{2}\rfloor -x_{j1}+t_i{t}_{j1}<\lfloor \frac{f_{j2}}{2}\rfloor -x_{j2}+t_i{t}_{j2}$$

$$\lfloor \frac{f_{j1}}{2}\rfloor -\lfloor \frac{f_{j2}}{2}\rfloor -x_{j1}+x_{j2}<t_i(t_{j2}-t_{j1})$$

注意到可能有 $t_{j2}-t_{j1}=0$（这为下文我的出锅埋下伏笔），根据上一篇题解的经验，我们拆分斜率的分子分母。实则 $t_{j2}-tj1\ge 0$
$$\frac{\lfloor \frac{f_{j1}}{2}\rfloor -\lfloor \frac{f_{j2}}{2}\rfloor -x_{j1}+x_{j2}}{(t_{j2}-t_{j1})}<t_i$$

$slope<t_i$ 且 $t_i$ 单调递增，和玩具装箱是同一种类型，维护单调递增斜率，最优决策取队首，每次决策扔队尾。

弹出决策点时，一定要记得写成小于等于的形式，对我这种写习惯了小于的人很不友好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;
}