題目傳送門：LOJ #3156。
題意簡述：
有一張 \(n\) 個點 \(m\) 條邊的有向圖，邊有兩個權值 \(p_i\) 和 \(q_i\)（\(p_i<q_i\)）表示若 \(p_i\) 時刻在這條邊的起點，則 \(q_i\) 時刻能到達這條邊的終點。
你需要規劃一條路線，使得從起點 \(1\) 號點出發，沿著這條路線到達終點 \(n\) 號點。
假設路線依次經過的邊為 \(\{a_1,a_2,\ldots,a_k\}\)，則需要保證 \(q_{a_{i-1}}\le p_{a_i}\)。
而這條路線的代價是 \(\displaystyle q_{a_k}+\sum_{i=2}^{k}f(p_{a_i}-q_{a_{i-1}})+f(p_{a_1})\)，其中 \(f(x)=\mathrm{A}x^2+\mathrm{B}x+\mathrm{C}\)。
你需要使得你規劃的路徑的代價最小，輸出這個最小代價。
題解：
轉移之間的代價是一個二次函數，這是顯然的斜率優化 DP 模型。
考慮 \(\mathrm{f}[i]\) 表示經過第 \(i\) 條邊后的 \(\sum f(p_{a_j}-q_{a_{j-1}})\)，化簡式子：
\[\begin{aligned}\mathrm{f}[i]&=\min_{y_j=x_i,q_j\le p_i}\{\mathrm{f}[j]+\mathrm{A}(p_i-q_j)^2+\mathrm{B}(p_i-q_j)+\mathrm{C}\}\\&=\min_{y_j=x_i,q_j\le p_i}\{\mathrm{f}[j]+\mathrm{A}p_i^2-2\mathrm{A}p_iq_j+\mathrm{A}q_j^2+\mathrm{B}p_i-\mathrm{B}q_j+\mathrm{C}\}\\&=\min_{y_j=x_i,q_j\le p_i}\{\mathrm{f}[j]+\mathrm{A}q_j^2-\mathrm{B}q_j-2\mathrm{A}p_iq_j\}+\mathrm{A}p_i^2+\mathrm{B}p_i+\mathrm{C}\end{aligned}\]
其中斜率的表達式是顯然的，\(x\) 坐標是 \(q_i\)，\(y\) 坐標是 \(\mathrm{f}[i]+\mathrm{A}q_i^2-\mathrm{B}q_i\)，令 \(\mathrm{D}_i=\mathrm{A}p_i^2+\mathrm{B}p_i+\mathrm{C}\)，
則 \(\displaystyle\mathrm{f}[i]=\mathrm{D}_i+\min_{y_j=x_i,q_j\le p_i}\{y_j-2\mathrm{A}p_ix_j\}\)。
考察兩個合法轉移點 \(j\) 和 \(k\)（\(x_j<x_k\)），轉移點 \(j\) 比轉移點 \(k\) 優當且僅當：
\[\begin{aligned}y_j-2\mathrm{A}p_ix_j&<y_k-2\mathrm{A}p_ix_k\\2\mathrm{A}p_i(x_k-x_j)&<y_k-y_j\\\frac{y_k-y_j}{x_k-x_j}&>2\mathrm{A}p_i\end{aligned}\]
因為不等號是大于號，所以維護下凸殼。
注意，為了方便，更新順序為按照 \(p_i\) 從小到大，這樣右側斜率是遞增的，但是并不能更新完立刻加入凸殼，而是應該等到輪到相應的 \(p_i\) 時再加入。
以下是代碼，時間復雜度為 \(\mathcal{O}(n+m+\max q)\)：
#include <cstdio>
#include <algorithm>
#include <vector>typedef double db;
const int MN = 100005, MM = 200005, MQ = 1005;int N, M, _A, _B, _C, Ans = 0x3f3f3f3f;
int d[MN], eu[MM], ev[MM], ep[MM], eq[MM];
std::vector<int> vp[MQ], vq[MQ];
int X[MM], Y[MM], f[MM];
int _stk[MM], *stk[MN], _l[MN], _r[MN];inline db Slope(int i, int j) {if (X[i] == X[j]) return Y[i] == Y[j] ? 0 : Y[i] < Y[j] ? 1e99 : -1e99;return (db)(Y[j] - Y[i]) / (X[j] - X[i]);
}int main() {freopen("route.in", "r", stdin);freopen("route.out", "w", stdout);scanf("%d%d%d%d%d", &N, &M, &_A, &_B, &_C);ev[0] = 1, vq[0].push_back(0), ++d[1];for (int i = 1; i <= M; ++i) {scanf("%d%d%d%d", &eu[i], &ev[i], &ep[i], &eq[i]);vp[ep[i]].push_back(i);vq[eq[i]].push_back(i);++d[ev[i]];}stk[0] = _stk;for (int i = 1; i <= N; ++i) stk[i] = stk[i - 1] + d[i - 1], _l[i] = 1;for (int t = 0; t <= 1000; ++t) {for (auto i : vq[t]) {int u = ev[i], *st = stk[u], l = _l[u], &r = _r[u];while (l < r && Slope(st[r - 1], st[r]) > Slope(st[r], i)) --r;st[++r] = i;if (u == N && Ans > f[i] + eq[i]) Ans = f[i] + eq[i];}for (auto i : vp[t]) {int u = eu[i], *st = stk[u], &l = _l[u], r = _r[u];while (l < r && Slope(st[l], st[l + 1]) < 2 * _A * t) ++l;if (l <= r) f[i] = Y[st[l]] - 2 * _A * t * X[st[l]] + _A * t * t + _B * t + _C;else f[i] = 0x3f3f3f3f;X[i] = eq[i], Y[i] = f[i] + _A * eq[i] * eq[i] - _B * eq[i];}}printf("%d\n", Ans);return 0;
}
)
