dp斜率优化
斜率优化本质上解决的是，给定一条直线的斜率和平面上的若干个点，要求选择一个点，使得该直线经过该点，且保证此时截距取到最小/最大值。
根据几何知识可以知道，如果要求截距的最小值，只要维护所有平面上的点的下凸包，把下凸包中的点按照横坐标从小到大排序，得到$(x_1,y_1),(x_2,y_2),…,(x_n,y_n)$，定义连续两个点之间的斜率$k_i=\frac{y_{i+1}-y_i}{x_{i+1}-x_i}$，那么$k_i$满足单调递增。如果给定的直线斜率为$k_0$，那么使得截距最小的点$a$一定满足$k_{a-1}\leqslant k_0\leqslant k_a$。
斜率优化就是把dp转移转化成这个几何问题，前驱状态$j$就是几何平面上的点，直线的斜率则由当前状态$i$决定，截距就是要最小/最大化的$dp[i]$。
比如说某个状态转移方程为
可以把它看成一条直线
于是状态转移方程也可以写成
可以发现$(x_j,y_j)$是由前驱状态$j$决定的，斜率$k_i$是当前状态$i$决定的，$b_i$即需要最小化的截距
这样优化之后，我们只需要考虑$(x_j,y_j)$在凸包上的那些点来进行转移，而不需要考虑平面上所有的点。
进一步优化，如果给出平面上点的顺序是按照横坐标从小到大给出的，那么维护凸包只需要$O(1)$维护一个关于斜率的单调栈即可。同时，如果斜率$k_i$也是按照从小到大的顺序给出的，那么把单调栈作为单调队列，当队首的斜率小于$k_i$时队首出列，那么找到满足截距最小的点$(x_j,y_j)$也是$O(1)$的。
$x_j$单调增和$k_i$单调增是最优的情况，但斜率优化并不要求这两个性质一定满足，如果$x_j$单调增不满足，可以用其他方法（平衡树/CDQ分治）维护凸包，如果$k_i$单调增不满足，则可以用二分之类的方法$O(lgn)$查找对应的$(x_j,y_j)$，所以还是挺灵活的。（一般来说会优先满足$x_j$的单调增，否则用其他方法维护凸包会比较困难）
写法和技巧
把状态转移方程转化成$b_i=y_j-k_ix_j$之后，先把$x,y,k,b$以及$dp[i]$求解的函数写出来
转移方程为
也就是
写出来就是
ll rx(ll i) { return r[i].x; }
ll ry(ll i) { return r[i].y; }
ll rp(ll i) { return r[i].p; }
ll rq(ll i) { return r[i].q; }
ll K(ll i) { return 2 * rp(i) * _A; }
ll X(ll j) { return rq(j); }
ll Y(ll j) { return dp[j] - rq(j) + _A * rq(j) * rq(j) - _B * rq(j); }
ll B(ll i, ll j) { return Y(j) - K(i) * X(j); }
ll Result(ll i, ll j) { return B(i, j) + rq(i) + _A * rp(i) * rp(i) + _B * rp(i) + _C; }
再把斜率函数写出来，如果会有相同的$x_j$，需要处理横坐标相同的情况，根据纵坐标的大小关系设置为$\pm \infty$，并且如果有横坐标相同的情况，调用斜率函数时需要注意两个参数的先后顺序，否则无穷大符号反过来就错了
double slope(ll i, ll j) {
if (X(i) == X(j)) {
return INF * (Y(i) <= Y(j));
} else return (double)(Y(i) - Y(j)) / (X(i) - X(j));
}
然后转移时根据$p_i$从小到大考虑，把点加入凸包的顺序根据$q_j$从小到大考虑，由于对于第$i$条路径，只需要考虑满足$q_j\leqslant p_i$的点，所以转移和加入点的顺序不同也是正确的。
由于只能从满足$y_j=x_i$的$j$转移，所以对于每个$y_j$都需要维护一个队列，由于deque常数比较大，可以用头指针head+vector的方法来维护单调队列。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6 + 5, M = 2e5 + 5, INF = 0x3f3f3f3f3f3f3f3f, inf = 0x3f3f3f3f;
ll n, m, _A, _B, _C, dp[N], ans = INF, ins[N];
vector<ll> q[M];
ll head[N];
struct Route {
ll x, y, p, q;
bool operator < (const Route &R) {
return p < R.p;
}
}r[N];
ll rx(ll i) { return r[i].x; }
ll ry(ll i) { return r[i].y; }
ll rp(ll i) { return r[i].p; }
ll rq(ll i) { return r[i].q; }
ll K(ll i) { return 2 * rp(i) * _A; }
ll X(ll j) { return rq(j); }
ll Y(ll j) { return dp[j] - rq(j) + _A * rq(j) * rq(j) - _B * rq(j); }
ll B(ll i, ll j) { return Y(j) - K(i) * X(j); }
ll Result(ll i, ll j) { return B(i, j) + rq(i) + _A * rp(i) * rp(i) + _B * rp(i) + _C; }
double slope(ll i, ll j) {
if (X(i) == X(j)) {
return INF * (Y(i) <= Y(j));
} else return (double)(Y(i) - Y(j)) / (X(i) - X(j));
}
ll rear(vector<ll> &V) { return (ll)V.size() - 1; }
signed main() {
scanf("%lld %lld %lld %lld %lld", &n, &m, &_A, &_B, &_C);
for (ll i = 1; i <= m; i++) {
scanf("%lld %lld %lld %lld", &r[i].x, &r[i].y, &r[i].p, &r[i].q);
}
sort(r + 1, r + 1 + m, [&](Route u, Route v) {
return u.p < v.p;
});
for (ll i = 1; i <= m; i++) ins[i] = i;
sort(ins + 1, ins + 1 + m, [&](ll u, ll v) {
return rq(u) < rq(v);
});
q[1].push_back(0);
ll j = 1;
for (ll i = 1; i <= m; i++) {
while(j <= m && rq(ins[j]) <= rp(i)) {
if (dp[ins[j]] == -1) {
j++;
continue;
}
ll nxt = ry(ins[j]);
ll &w = head[nxt];
vector<ll> &W = q[nxt];
while(w < rear(W) && slope(W[rear(W) - 1], W[rear(W)]) >= slope(W[rear(W)], ins[j])) W.pop_back();
W.push_back(ins[j]);
j++;
}
ll pre = rx(i);
ll &h = head[pre];
vector<ll> &Q = q[pre];
if (Q.size() == 0) {
dp[i] = -1;
} else {
while(h < rear(Q) && slope(Q[h], Q[h + 1]) < K(i)) h++;
dp[i] = Result(i, Q[h]);
if (ry(i) == n) {
ans = min(ans, dp[i]);
}
}
}
cout << ans << endl;
return 0;
}
其他题目
基础模板题P3195 [HNOI2008]玩具装箱
求最大值，维护上凸包（有时候满足单调性但是是反的，可以给k和x同时加负号）P3628 [APIO2010]特别行动队
结合滚动数组B. Cats Transport