马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
主要是因为，在洛谷大部分题解都是写李超线段树优化的，看到标签我也被诈骗了，推完式子才发现具有单调的良好性质。遂写一篇典范的斜率优化 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;
- }
|
