斜率倒闭了怎么办 /jk
小屹0_0
·
·
算法·理论
前言
扶苏倒闭了怎么办 /jk。
更新于 2026/7/8：@AIerqwq 指出一个式子出了问题。
斜率优化是什么
是啊，是什么。
斜率优化是一种优化 1D 动态规划的东西。
:::info[什么是 1D 动态规划？]
1D 动态规划是一类动态规划问题，规划的状态是一维的，暴力转移可做到 O(n^2)。
注意此时不一定可以使用斜率优化，斜率优化只能解决部分问题。
:::
:::info[一般什么类型的转移方程可以用斜率优化？]
转移中带有 i 和 j 的乘积的，具体可以看下面。
:::
具体的，其转移方程可能是：
f_i = \max\limits_{j \leq i} \{ f_j + g(j) + h(j) \times p(i) + q(i) \}
其中 g，h，p，q 都是函数，\max 不固定，也可以是 \min。
不妨设最优决策点为 j，那么：
f_i = g_j + g(j) + h(j) \times p(i) + q(i)
将只与 i 有关的项移项。
f_i - q(i) = f_j + g(j) + h(j) \times p(i)
此时来到了斜率优化的核心：把这个问题抽象成一条直线在往很多点上靠。
我们考虑 y = kx + b 这个式子，移项得到 b = y - kx（updated）。
我们想象 b = f_i - q(i)，那我们就在最大化截距。
我们令 k = p(i)，那么就是一条直线，在很多 (x, y) 中选择一个，将这条直线移动，直到穿过这个点，计算截距。
然后根据我们的转移，得到 x = h(j)，y = f_j + g(j)，然后发现这两个是确定的，也就是 (x, y) 这个点是确定的。
于是，所有定点里创造了最大的截距的就是最优转移点。
不难发现，这个点一定位于上凸壳上。
所以我们维护一个上凸壳（如果是 \min 只需要换成下凸壳）每次找到最优决策点即可。
此处有分支……
如果 x 单调
此时如果 k 忽大忽小，可以二分找到最优决策点，因为最优决策点一定是第一个满足当前点与凸壳上下一个点的斜率小于 k 的第一个点。
如果 k 单调就可以用栈或双端队列，每次因为最优决策点都是往同一个方向移动，直接弾栈即可。
如果 x 不单调
此时需要一些数据结构加持，CDQ 分治闪亮登场。
在 CDQ 分治的过程中我们只需要统计左半边给右半边的贡献，因此可以直接将左半边的 x 排序然后求凸壳。
至于 k 是否忽大忽小的影响，和上面一样。
例题
P5504
P5504
题意：将序列分为若干段，每一段选出一个颜色 col，然后计算这一段这个颜色的出现次数 cnt，使得 \sum col \times cnt^2。
显然，区间 l \sim r 的 col 一定是 s_l，并且 s_l = s_r。
我们令 f_i 表示划分的最后一个段的右端点是 i 且 1 \sim i 已经分割完毕的方案数。
于是 f_i = \max\limits_{j \leq i, s_{j} = s_i} \{ f_{j-1} + s_i \times cnt(s_i, j, i)^2 \}。
我们假设 $f_i = f_j + s_i \times cnt(s_i, j, i)^2$，统计一个前缀和 $pre_i$ 表示对于所有的 $1 \leq j \leq i$，$s_j = s_i$ 的个数。
于是 $f_i = f_{j-1} + s_i \times (pre_i - pre_j + 1)^2$。
大力推推推！
$$
\begin{aligned}
f_i &= f_{j - 1} + s_i \times (pre_i^2 - 2 pre_i pre_j + pre_j^2 + 2pre_i + 1 - 2pre_j) \\
&= f_{j - 1} + s_i \cdot pre_i^2 - 2s_ipre_ipre_j + s_ipre_j^2 + 2s_i pre_i + s_i - 2s_i pre_j \\
&= f_{j - 1} + s_i \cdot pre_i^2 - 2s_ipre_ipre_j + s_jpre_j^2 + 2s_i pre_i + s_i - 2s_j pre_j
\end{aligned}
$$
将只与 $i$ 有关的和常数项移项。
$$
f_i - s_i \cdot pre_i^2 - 2s_i pre_i - s_i = f_{j - 1} + 2s_ipre_ipre_j + s_j \cdot pre_j^2 - 2s_j pre_j
$$
根据斜截式整理：
$$
(f_i - s_i \cdot pre_i^2 - 2s_i pre_i - s_i) = (f_{j - 1} + s_j \cdot pre_j^2 - 2s_j pre_j) + 2s_ipre_ipre_j
$$
我们令 $b = f_i - s_i \cdot pre_i^2 - 2s_ipre_i - s_i$，那么我们就是求 $\max b$，也就是截距最大值。
根据之前所说，我们将 $y$ 设为只和 $j$ 有关的项，$k$ 设为乘积中和 $j$ 无关的项，$x$ 设为乘积中与 $j$ 有关的项。
于是：
$$
\begin{cases}
b = f_i - s_i \cdot pre_i^2 - 2s_ipre_i - s_i \\
y = f_{j - 1} + s_j \cdot pre_j^2 - 2s_jpre_j \\
k = 2s_i \cdot pre_i \\
x = pre_j
\end{cases}
$$
对于每一个颜色，维护上凸壳（因为是求 $\max$）最后我们来观察答案应该在哪里取到。
显然，斜率 $k$ 是递增的，随着斜率 $k$ 递增，我们发现最优决策点不断向前移动（可画图感受）。
于是这个题目就到此结束了。
此外，本题的 $j$ 是小于等于 $i$ 而非小于 $i$，所以要先加入 $i$ 到上凸壳中再进行决策。
`int` 类型函数没写返回值倒闭了怎么办 /jk。
:::success[code]
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
const int N = 2e5 + 5, M = 1e4 + 5;
const int inf = 1e9, mod = 998244353;
int n, f[N], lst[M];
int s[N], pre[N];
vector <int> vec[M];
inline int X(int i){
return pre[i];
}
inline int Y(int i){
return f[i - 1] + s[i] * pre[i] * pre[i] - 2 * s[i] * pre[i];
}
inline pii slope(int i, int j){
return {Y(i) - Y(j), X(i) - X(j)};
}
inline bool cmp(pii a, pii b){
if (a.se * b.se > 0) return a.fi * b.se < b.fi * a.se;
return a.fi * b.se > b.fi * a.se;
}
inline void calc(int i, int j){
f[i] = f[j - 1] + 1ll * s[i] * (pre[i] - pre[j] + 1) * (pre[i] - pre[j] + 1);
}
void init(){
}
void solve(){
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> s[i], pre[i] = pre[lst[s[i]]] + 1, lst[s[i]] = i;
for (int i = 1; i <= n; i ++ ){
int k = 2 * s[i] * pre[i];
while (vec[s[i]].size() >= 2 && cmp(slope(vec[s[i]][vec[s[i]].size() - 2], vec[s[i]][vec[s[i]].size() - 1]), slope(vec[s[i]][vec[s[i]].size() - 1], i))) vec[s[i]].pop_back();
vec[s[i]].push_back(i);
while (vec[s[i]].size() >= 2 && !cmp({k, 1}, slope(vec[s[i]][vec[s[i]].size() - 2], vec[s[i]][vec[s[i]].size() - 1]))) vec[s[i]].pop_back();
calc(i, vec[s[i]].back());
}
cout << f[n] << "\n";
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T = 1; //cin >> T;
while (T -- ) init(), solve();
}
```
:::
### P6302
[P6302](https://www.luogu.com.cn/problem/P6302)
~~NOI 倒闭了怎么办 /jk。~~
首先我们按照 $p$ 排序，这么排序有两个好处，第一个好处是使得我们的 DP只会从前面的状态转移来，其二是为了应对 $q_{s_j} \leq p_{s_{j + 1}}$。
设 $f_i$ 为乘坐的最后一班车为 $i$ 的最小烦躁值。
$$
f_i = \min\limits_{j \leq i, y_j = x_i, q_j \leq p_i} \{ f_{j-1}+ A(p_i - q_j)^2 + B(p_i - q_j) + C \}
$$
设最优转移点是 $j$，那么：
$$
\begin{aligned}
f_i &= f_{j}+ A(p_i - q_j)^2 + B(p_i - q_j) + C \\
&= f_{j}+ A(p_i^2 - 2p_iq_j + q_j^2) + Bp_i - Bq_j + C \\
&= f_{j}+ Ap_i^2 - 2Ap_iq_j + Aq_j^2 + Bp_i - Bq_j + C
\end{aligned}
$$
将只与 $i$ 有关的和常数项移项。
$$
f_{i} - Ap_i^2 - Bp_i - C = f_{j} + 2Ap_iq_j + Aq_j^2 - Bq_j
$$
根据斜截式整理：
$$
(f_{i} - Ap_i^2 - Bp_i - C) = (f_{j} + Aq_j^2 - Bq_j) + 2Ap_iq_j
$$
我们令 $b = f_{i} - Ap_i^2 - Bp_i - C$，那么我们就是求 $\min b$，也就是截距最小值。
我们将 $y$ 设为只和 $j$ 有关的项，$k$ 设为乘积中和 $j$ 无关的项，$x$ 设为乘积中与 $j$ 有关的项。
$$
\begin{cases}
b = f_{i} - Ap_i^2 - Bp_i - C \\
y = f_{j} + Aq_j^2 - Bq_j \\
k = 2Ap_i \\
x = q_j
\end{cases}
$$
由于我们按照 $p$ 排序了，所以 $k$ 递增。
又因为要求 $\min$，所以是一个下凸壳。
然后画图发现我们的决策点在向后移动，所以是维护双端队列。
然后就结束了……吗？这题还有限制 $y_j = x_i$ 和 $q_j \leq p_i$。
对于第一个限制，和上一个题目是一样的，我们对于每一个 $i$ 压入 $y_i$ 对应的双端队列即可。
然后这样无法解决 $q_j \leq p_i$。但是我们让 $p$ 排序了，所以我们只需要不第一时间压入双端队列而是在从小到大遍历每一个 $i$，的同时将 $q_j \leq p_i$ 的点全部压入该压入的双端队列。
这样就是真的结束了。
:::success[code]
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
const int N = 1e6 + 5, M = 1e6 + 5;
const int inf = 1e9, mod = 998244353;
const ll INF = 1e18;
int n, m, A, B, C, f[N];
struct node{
int p, q, x, y;
} a[N];
struct deq{
int qh;
vector <int> v;
deq(){ qh = 0; }
int size(){ return v.size() - qh; }
void push_back(int x){ v.push_back(x); }
void pop_back(){ v.pop_back(); }
void pop_front(){ qh ++; }
int back(){ return v.back(); }
const int operator [](const int &x){ return v[qh + x]; }
} vec[N];
int X(int i){
return a[i].q;
}
int Y(int i){
return f[i] + A * a[i].q * a[i].q - B * a[i].q;
}
pii slope(int i, int j){
if (X(i) == X(j)){
if (Y(i) > Y(j)) return {-inf, 1};
return {inf, 1};
}
return {Y(i) - Y(j), X(i) - X(j)};
}
bool cmp(pii a, pii b){
bool flg = (a.se < 0) ^ (b.se < 0);
if (flg) return a.fi * b.se > b.fi * a.se;
return a.fi * b.se < b.fi * a.se;
}
void calc(int i, int j){
f[i] = f[j] + A * (a[i].p - a[j].q) * (a[i].p - a[j].q) + B * (a[i].p - a[j].q) + C;
}
void psh(int x){
// return ;
auto &qwq = vec[a[x].y];
while (qwq.size() >= 2 && !cmp(slope(qwq[qwq.size() - 2], qwq[qwq.size() - 1]), slope(qwq[qwq.size() - 1], x))) qwq.pop_back();
qwq.push_back(x);
}
void init(){
}
void solve(){
cin >> n >> m >> A >> B >> C;
for (int i = 1; i <= m; i ++ ) cin >> a[i].x >> a[i].y >> a[i].p >> a[i].q;
sort(a + 1, a + m + 1, [&](node x, node y){
return x.p < y.p;
});
priority_queue <pii, vector <pii>, greater <pii>> q;
vec[1].push_back(0);
// for (int i = 1; i <= n; i ++ ) vec[i].push_back(0);
for (int i = 1; i <= m; i ++ ){
// if (i == 2) return ;
while (q.size() && q.top().fi <= a[i].p) psh(q.top().se), q.pop();
// if (i == 2) return ;
auto &qwq = vec[a[i].x];
int k = 2 * A * a[i].p;
// if (i == 2) return ;
while (qwq.size() >= 2 && !cmp({k, 1}, slope(qwq[0], qwq[1]))) qwq.pop_front();
// if (!qwq.size()){
// cout << i << "\n";
// return ;
// }
f[i] = INF;
if (!qwq.size()) continue;
int j = qwq[0]; calc(i, j);
q.push({a[i].q, i});
// if (i == 2) return ;
}
int mn = INF;
for (int i = 1; i <= m; i ++ )
if (a[i].y == n){
mn = min(mn, f[i] + a[i].q);
// cout << i << " " << f[i] << " " << a[i].q << "\n";
}
cout << mn << "\n";
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T = 1; //cin >> T;
while (T -- ) init(), solve();
}
```
:::
### P7926
[P7926](https://www.luogu.com.cn/problem/P7926)
这题数据倒闭了怎么办 /jk。
设 $f_i$ 表示将前 $i$ 个分好段了的方案数。
$$
f_i = \min\limits_{j \leq i} \{ f_{j - 1} + (pre_i - pre_{j - 1} - L)^2 \}
$$
诶，然后你发现这个玩意要求最小和次小，于是你设 $f_{i, 0 / 1}$ 表示第 $i$ 个的最小答案和次小答案。
然后有转移：
$$
f_{i, 0} = \min\limits_{j \leq i} \{ f_{j - 1, 0} + (pre_i - pre_{j - 1} - L)^2 \} \\
f_{i, 1} = \min \{ \min\limits_{j \leq i} \{ f_{j - 1, 1} + (pre_i - pre_{j - 1} - L)^2 \}, \operatorname{nxt}_{j \leq i} \{ f_{j - 1, 0} + (pre_i - pre_{j - 1} - L)^2 \} \}
$$
~~然后就会有一个人在机房惊呼我去这咋做！？DP 倒闭了怎么办 /jk。~~
第一个式子就是显然的斜率优化，第二个呢？
然后你会发现第二个的第一种也是简单斜率优化。
:::info[如果你想看这个“简单”部分的式子]{open}
由于 $f_{i, 0}$ 的转移和 $f_i{, 1}$ 的第一部分是一样的，只是 $0 \rightarrow 1$ 而已，于是令 $f_i$ 为你要算的。
$$
f_i = \min \{ f_{j - 1} + (pre_i - pre_{j - 1} - L)^2 \}
$$
假设最优转移点在 $j$，那么：
$$
\begin{aligned}
f_i &= f_{j - 1} + (pre_i - pre_{j - 1} - L)^2 \\
&= f_{j - 1} + pre_i^2 + pre_{j - 1}^2 + L^2 - 2pre_ipre_{j - 1} - 2Lpre_i + 2Lpre_{j - 1} \\
\end{aligned}
$$
移项，得到：
$$
(f_i - pre_i^2 - L^2 + 2Lpre_i) = (f_{j - 1} + pre_{j - 1}^2 + 2Lpre_{j - 1}) - 2pre_ipre_{j - 1}
$$
于是：
$$
\begin{cases}
b = f_i - pre_i^2 - L^2 + 2Lpre_i \\
y = f_{j - 1} + pre_{j - 1}^2 + 2Lpre_{j - 1} \\
k = 2pre_i \\
x = pre_{j - 1}
\end{cases}
$$
$k$ 递增，维护的是下凸壳，最优决策点向右，所以是双端队列。
:::
那第二个的第二种呢？
不难发现，第二大的点不一定就在凸壳上最优决策点的两端。
这里给个图，因为不好理解了。
如图，黄色的是凸壳（$ABCD$），红色的是凸壳中舍去的点（$KLM$）。直线 $BF$ 是最优，$NL$ 是次优的。
而你发现 $NL$ 其实不是 $B$ 两端的 $A$ 或是 $C$，而是 $f_{i, 0}$ 组成的凸包中被舍弃的点中的最优决策点。
为了方便叙述，我们设 $f_{i, 0}$ 组成的凸包是 $t_1$，而 $f_{i, 1}$ 组成的是 $t_2$，$f_{i, 0}$ 舍弃的组成的是 $t_3$。
那么 $t_1$ 和 $t_2$ 不用多说，$t_3$ 怎么搞。
不难发现 $t_1$ 每次弾栈都需要对 $t_3$ 进行更新。
首先，$t_1$ 的最后一个点的 $x$ 坐标一定比 $t_3$ 的最后一个点的 $x$ 坐标大，否则 $t_3$ 的最后一个点肯定可以加入 $t_1$ 中。
然后，不难发现，$t_1$ 每次会被弹出一个连续后缀，而这个后缀会直接断掉 $t_3$ 的一个后缀。
原因是我们首先会断掉 $t_3$ 中横坐标大于 $t_1$ 中断掉后缀的第一个点的横坐标的所有点，因为 $t_3$ 是 $t_1$ 淘汰掉的，所以显然直接插进去更优。
然后就可以直接用 $t_1$ 中第一个点去淘汰 $t_3$ 中暂未断掉的部分的后缀，然后就直接每个点依次加入并维护凸包即可。
当然这里官解不知道是不是脑抽写了一个 $O(n \log n)$ 的，反正我的是 $O(n)$ 的，完全不需要二分这个点啊。
注意如果这次斜率没有弹出凸包中任何一个点，那么需要拿上次弹出的最后一个点（如果存在）尝试更新次小值。
$O(n)$ 写法就是一大坨，如果想要不那么大就可以去看出题人题解。
:::success[code]
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
const int N = 2e5 + 5, M = 1e6 + 5;
const int inf = 1e9, mod = 998244353;
const ll INF = 1e18;
int n, L, a[N], f[N][2], pre[N];
// X1 -> f[i][0]
// X2 -> f[i][1]
// X3 -> f[i][0] pass
deque <int> q1, q2, q3;
int X1(int i){
return pre[i - 1];
}
int Y1(int i){
return f[i - 1][0] + pre[i - 1] * pre[i - 1] + 2 * pre[i - 1] * L;
}
int X2(int i){
return pre[i - 1];
}
int Y2(int i){
return f[i - 1][1] + pre[i - 1] * pre[i - 1] + 2 * pre[i - 1] * L;
}
int X3(int i){
return pre[i - 1];
}
int Y3(int i){
return f[i - 1][0] + pre[i - 1] * pre[i - 1] + 2 * pre[i - 1] * L;
}
pii slope1(int i, int j){
return {Y1(i) - Y1(j), X1(i) - X1(j)};
}
pii slope2(int i, int j){
return {Y2(i) - Y2(j), X2(i) - X2(j)};
}
pii slope3(int i, int j){
return {Y3(i) - Y3(j), X3(i) - X3(j)};
}
bool cmp(pii a, pii b){
bool flg = (a.se < 0) ^ (b.se < 0);
if (flg) return 1.0 * a.fi * b.se > 1.0 * b.fi * a.se;
return 1.0 * a.fi * b.se < 1.0 * b.fi * a.se;
}
void init(){
}
void solve(){
cin >> n >> L;
for (int i = 1; i <= n; i ++ ) cin >> a[i], pre[i] = pre[i - 1] + a[i];
for (int i = 0; i <= n; i ++ ) f[i][0] = f[i][1] = INF;
f[0][0] = 0;
int lsta = -1, lstb = -1;
for (int i = 1; i <= n; i ++ ){
vector <int> v;
while (q1.size() >= 2 && !cmp(slope1(q1[q1.size() - 2], q1[q1.size() - 1]), slope1(q1[q1.size() - 1], i))) v.push_back(q1[q1.size() - 1]), q1.pop_back();
q1.push_back(i);
while (q2.size() >= 2 && !cmp(slope2(q2[q2.size() - 2], q2[q2.size() - 1]), slope2(q2[q2.size() - 1], i))) q2.pop_back();
q2.push_back(i);
if (v.size()){
while (q3.size() && X3(q3[q3.size() - 1]) >= X3(v[v.size() - 1])) q3.pop_back();
while (q3.size() >= 2 && !cmp(slope3(q3[q3.size() - 2], q3[q3.size() - 1]), slope3(q3[q3.size() - 1], v[v.size() - 1]))) q3.pop_back();
while (v.size()) q3.push_back(v[v.size() - 1]), v.pop_back();
}
if (i == 1){
f[i][0] = (a[i] - L) * (a[i] - L);
f[i][1] = INF;
}
else{
int k = 2 * pre[i], j = 0;
if (q1.size() < 2 || cmp({k, 1}, slope1(q1[0], q1[1]))){
if (lsta != -1){
j = lsta;
f[i][1] = min(f[i][1], f[j - 1][0] + (pre[i] - pre[j - 1] - L) * (pre[i] - pre[j - 1] - L));
}
}
while (q1.size() >= 2 && !cmp({k, 1}, slope1(q1[0], q1[1]))){
j = q1[0], lsta = j;
// cout << i << ",1 from " << j << ",0 q1\n";
f[i][1] = min(f[i][1], f[j - 1][0] + (pre[i] - pre[j - 1] - L) * (pre[i] - pre[j - 1] - L));
q1.pop_front();
}
if (q1.size()){
j = q1[0];
// cout << i << ",0 from " << j << ",0 q1\n";
f[i][0] = min(f[i][0], f[j - 1][0] + (pre[i] - pre[j - 1] - L) * (pre[i] - pre[j - 1] - L));
}
if (q1.size() > 1){
j = q1[1], lstb = j;
// cout << i << ",1 from " << j << ",0 q1\n";
f[i][1] = min(f[i][1], f[j - 1][0] + (pre[i] - pre[j - 1] - L) * (pre[i] - pre[j - 1] - L));
}
else{
if (lstb != -1){
j = lstb;
f[i][1] = min(f[i][1], f[j - 1][0] + (pre[i] - pre[j - 1] - L) * (pre[i] - pre[j - 1] - L));
}
}
while (q2.size() >= 2 && !cmp({k, 1}, slope2(q2[0], q2[1]))) q2.pop_front();
if (q2.size()){
j = q2[0];
// cout << i << ",1 from " << j << ",1 q2\n";
f[i][1] = min(f[i][1], f[j - 1][1] + (pre[i] - pre[j - 1] - L) * (pre[i] - pre[j - 1] - L));
}
while (q3.size() >= 2 && !cmp({k, 1}, slope3(q3[0], q3[1]))) q3.pop_front();
if (q3.size()){
j = q3[0];
// cout << i << ",1 from " << j << ",0 q3\n";
f[i][1] = min(f[i][1], f[j - 1][0] + (pre[i] - pre[j - 1] - L) * (pre[i] - pre[j - 1] - L));
}
}
}
cout << f[1][0] << "\n";
for (int i = 2; i <= n; i ++ ) cout << f[i][0] << " " << f[i][1] << "\n";
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T = 1; //cin >> T;
while (T -- ) init(), solve();
}
```
:::
### P8632
[P8632](https://www.luogu.com.cn/problem/P8632)
前排提示：下文中令 $a_i = d_i$。
记 $ans(l, r, x)$ 为 $l \sim r$ 中的家庭走到距离起点 $x$ 的位置的距离，显然可以用前缀和 $O(1)$ 求。
首先一个重要的观察是我们不会在两户人家中间选择举办地，除了 $p_4 = L$ 以外所有举办地都选在某个家庭所在位置。
那么我们设 $f_{i, j}$ 表示到 $i$ 为止，建了几个举办地，其中 $1 \leq j \leq 3$，最后只需要枚举哪个点是 $p_3$，计算 $f_i + ans(p_3 + 1, n, L)$ 的最小值。
显然 $f_{i, 1}$ 等于 $ans(1, i, a_i)$。
只需要计算 $f_{i, 2}$ 和 $f_{i, 3}$ 即可。
先计算 $f_{i, 2}$，有 $f_{i, 2} = \min\limits_{j < i} \{ f_{j, 1} + ans(j + 1, i, a_i) \}$。
此时令 $pre_i = \sum\limits_{1 \leq j \leq i} a_j t_j$，$cnt_i = \sum\limits_{1 \leq j \leq i} t_j
然后表示一下 ans(l, r, x)，不难发现等于 x \times (cnt_r - cnt_{l - 1}) - (pre_r - pre_{l - 1})。
那么带入：
f_{i, 2} = \min\limits_{j < i} \{ f_{j, 1} + a_i \times (cnt_i - cnt_j) - (pre_i - pre_j) \}
假设 j 是最优决策点，那么：
\begin{aligned}
f_{i, 2} &= f_{j, 1} + a_i \times (cnt_i - cnt_j) - (pre_i - pre_j) \\
&= f_{j, 1} + a_i \times cnt_i - a_i \times cnt_j - pre_i + pre_j
\end{aligned}
移项，得到：
f_{i, 2} - a_i \times cnt_i + pre_i = f_{j, 1} - a_i \times cnt_j + pre_j
整理：
(f_{i, 2} - a_i \times cnt_i + pre_i) = (f_{j, 1} + pre_j) - a_i \times cnt_j
然后套路的，令：
\begin{cases}
b = f_{i, 2} - a_i \times cnt_i + pre_i \\
y = f_{j, 1} + pre_j \\
k = a_i \\
x = cnt_j \\
\end{cases}
然后直接斜率优化搞一搞，这里还是要讨论决策点。
这个 x 就不必多说了，显然递增。
那么最小值，维护下凸壳，斜率递增，决策点向后移，只需要维护双端队列即可。
$f_{i, 3}$ 没啥区别，复制粘贴的事情罢了。
### P2497
[P2497](https://www.luogu.com.cn/problem/P2497)
我寻思我讲了半天怎么全是板子啊？做板子倒闭了怎么办 /jk。
于是出现了这个题。
~~其实还是板子 qwq。~~
首先推一推式子，如果 $j \rightarrow i$ 那么 $r'_i$ 是多少。
$$
\begin{aligned}
(r'_i + r_j)^2 &= (x_i - x_j)^2 + (r'_i - r_j)^2 \\
(r'_i + r_j)^2 &= (x_i - x_j)^2 + (r'_i - r_j)^2 \\
2r'_ir_j &= (x_i - x_j)^2 - 2r_ir_j \\
4r'_ir_j &= (x_i - x_j)^2 \\
r'_i &= \frac{(x_i - x_j)^2}{4r_j}
\end{aligned}
$$
于是 $\sqrt{r'_i} = \frac{(x_i - x_j)}{2\sqrt{r_j}}$。
先对 $x_i$ 排序，然后设 $f_i$ 表示前 $i$ 个，最后连接了 $i$ 的最小花费。
答案直接从发射范围满足条件的所有点中的 $f_i$ 中取最小值。
那么，有：
$$
f_1 = v_1 \\
f_i = \min\limits_{1 \leq j < i} \{ f_j + \frac{x_i - x_j}{2 \sqrt{r_j}} + v_i \}
$$
套路的去掉 $\min$：
$$
f_i = f_j + \frac{x_i - x_j}{2 \sqrt{r_j}} + v_i
$$
移项：
$$
f_i - v_i = f_j + \frac{x_i}{2 \sqrt{r_j}} - \frac{x_j}{2 \sqrt{r_j}}
$$
整理：
$$
(f_i - v_i) = (f_j - \frac{x_j}{2 \sqrt{r_j}}) + \frac{x_i}{2 \sqrt{r_j}}
$$
然后就可以设出：
$$
\begin{cases}
b = f_i - v_i \\
y = f_j - \frac{x_j}{2 \sqrt{r_j}} \\
k = x_i \\
x = \frac{1}{2 \sqrt{r_j}} \\
\end{cases}
$$
根据一开始所讲，$k$ 递增但 $x$ 不递增，CDQ 分治闪亮登场！
好了另一个模版题到此结束。
咋全是模版题。
以及这题太肝了，一下午三个小时才肝出来，倒是一遍过了。
:::success[code]
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
const int N = 5e5 + 5, M = 1e6 + 5;
const int inf = 1e9, mod = 998244353;
const ll INF = 1e18;
int n, m;
struct node{
int x, r, v, id;
double f;
} a[N];
long double X(node a){
return 1.0 / 2.0 / sqrt(a.r);
}
long double Y(node a){
return a.x / 2.0 / sqrt(a.r) - a.f;
}
long double slope(int i, int j){
return (Y(a[j]) - Y(a[i])) / (X(a[j]) - X(a[i]));
}
bool cmpx(node a, node b){
return a.x < b.x;
}
bool cmpX(node a, node b){
return X(a) < X(b);
}
bool cmpid(node a, node b){
return a.id < b.id;
}
void cdq(int l, int r){
if (l == r){
// cout << "sured " << l << " : " << a[l].f << "\n";
return ;
}
int mid = (l + r) >> 1;
cdq(l, mid);
sort(a + l, a + mid + 1, cmpX);
// sort(a + l, a + mid + 1, [&](node qwq, node pwp){
// int xqwq = 1.0 / 2.0 / sqrt(qwq.r);
// int xpwp = 1.0 / 2.0 / sqrt(pwp.r);
// return xqwq < xpwp;
// });
// sort(a + l, a + mid + 1, cmpX);
deque <int> q;
for (int i = l; i <= mid; i ++ ){
while (q.size() >= 2 && slope(q[q.size() - 2], q[q.size() - 1]) <= slope(q[q.size() - 1], i)) q.pop_back();
q.push_back(i);
}
// cout << l << "," << mid << "," << r << "\n";
// for (int i = 0; i < q.size(); i ++ ) cout << q[i] << " ";
// cout << "\n";
for (int i = mid + 1; i <= r; i ++ ){
double k = a[i].x;
while (q.size() >= 2 && k >= slope(q[q.size() - 2], q[q.size() - 1])) q.pop_back();
int j = q.back();
a[i].f = min(a[i].f, a[j].f + (a[i].x - a[j].x) / 2.0 / sqrt(a[j].r) + a[i].v);
}
// sort(a + l, a + mid + 1, cmpid);
cdq(mid + 1, r);
}
void init(){
}
void solve(){
cin >> n >> m;
for (int i = 1; i <= n; i ++ ){
cin >> a[i].x >> a[i].r >> a[i].v;
a[i].id = i;
a[i].f = INF;
}
// sort(a + 1, a + n + 1);
// for (int i = 1; i <= n; i ++ ) a[i].id = i;
a[1].f = a[1].v;
cdq(1, n);
double mn = INF;
for (int i = 1; i <= n; i ++ ) if (a[i].x + a[i].r >= m) mn = min(mn, a[i].f);
cout << fixed << setprecision(3) << mn << "\n";
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T = 1; //cin >> T;
while (T -- ) init(), solve();
}
```
:::