（斜率优化）洛谷 P8726 蓝桥杯 2020 省 AB3 旅行家 题解
主要是因为，在洛谷大部分题解都是写李超线段树优化的，看到标签我也被诈骗了，推完式子才发现具有单调的良好性质。遂写一篇典范的斜率优化 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,x;
ll f,q;
ll slope_up(ll j1,ll j2)
{
return f/2-f/2-x+x;
}
ll slope_down(ll j1,ll j2)
{
return t-t;
}
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&t);
for(int i=1;i<=n;i++)
scanf("%lld",&x);
ll hh=0,tt=0;
q=1;
ll ans=-inf;
for(int i=2;i<=n;i++)
{
while(hh<tt&&slope_up(q,q)<t*slope_down(q,q))hh++;
f=f]/2-x]+t*t];
while(hh<tt&&slope_up(q,i)*slope_down(q,q)<=slope_up(q,q)*slope_down(q,i))tt--;
q[++tt]=i;
}
for(int i=1;i<=n;i++)
ans=max(ans,f);
cout<<ans;
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]