P5468回家路线如何规划？
摘要：P5468 [NOI2019] 回家路线 大意 从 (1) 号点到第 (n) 号点，每个地方是一个站点，有 (k) 条路线，每个路线的车都有起始点和到达点，起始时间和到达时间，在等车的过程中他会哈气，问哈气值最小是什么？ 思路
P5468 [NOI2019] 回家路线
大意
从 \(1\) 号点到第 \(n\) 号点，每个地方是一个站点，有 \(k\) 条路线，每个路线的车都有起始点和到达点，起始时间和到达时间，在等车的过程中他会哈气，问哈气值最小是什么？
思路
我们发现如果我们按时间进行排序，处理每个站点的航线的话，我们发现这样的话，后面的站点只能从前航线时间转移过来，那么这样的话我们做 DP 是没有后效性的，我们的转移是这样的，对于一个站点，若两条航线 \(v_j = u_i\)，那么有：
\[dp[i] = \min_{j \in \text{valid}} \{ dp[j] + A(p_i - q_j)^2 + B(p_i - q_j) + C \}
\]
我们不妨把这个转移式子拆开：
\[dp[i] = dp[j] + Ap_i^2 - 2Ap_iq_j + Aq_j^2 + Bp_i - Bq_j + C
\]
再把和 \(i\) 与 \(j\) 有关的项分开：
\[dp[i] = \underbrace{(dp[j] + Aq_j^2 - Bq_j)}_{\text{跟 } j \text{ 有关}} - \underbrace{2Ap_iq_j}_{i, j \text{ 混合}} + \underbrace{(Ap_i^2 + Bp_i + C)}_{\text{跟 } i \text{ 有关}}
\]
我们发现其实是可以做斜率优化的，我们将其化为 \(y = kx + b\) 的形式：
\[\underbrace{dp[j] + Aq_j^2 - Bq_j}_{y} = \underbrace{(2Ap_i)}_{k} \cdot \underbrace{q_j}_{x} + \underbrace{(dp[i] - Ap_i^2 - Bp_i - C)}_{b}
\]
接下来维护一个下凸壳即可，由于是静态的，我们可以考虑直接用单调队列维护，但是有个很大的问题是，这些站点的东西要混起来吗？？？那怎么能知道哪个站点的能转移的点在哪呢？很简单的方式就是，我们直接维护 \(n\) 个单调队列即可。每次对于每个站点进行转移即可。
代码
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
#define ll long long
const int MAXN = 2 * 1e5 + 5;
int n, m;
ll A, B, C;
ll u[MAXN], v[MAXN], q[MAXN], p[MAXN], dp[MAXN];
int id1[MAXN], id2[MAXN];
deque<int> Q[MAXN >> 1];
double X(int x){
return q[x];
}
double Y(int x){
return dp[x] + A * q[x] * q[x] - B * q[x];
}
double slope(int a, int b){
if(X(a) == X(b)) return Y(a) >= Y(b) ? 1e18 : -1e18;
return (Y(a) - Y(b)) / (X(a) - X(b));
}
bool cmp1(int a, int b){
return p[a] < p[b];
}
bool cmp2(int a, int b){
return q[a] < q[b];
}
int main(){
// freopen("rout.in", "r", stdin);
// freopen("rout.out", "w", stdout);
cin.tie(0) -> ios::sync_with_stdio(0);
cin >> n >> m >> A >> B >> C;
for(int i = 1;i <= m;i ++){
cin >> u[i] >> v[i] >> p[i] >> q[i];
id1[i] = id2[i] = i;
dp[i] = 1e18;
}
sort(id1 + 1, id1 + m + 1, cmp1);
sort(id2 + 1, id2 + m + 1, cmp2);
dp[0] = q[0] = 0; v[0] = 1;
Q[1].push_back(0);
int nxt = 1;
for(int k = 1;k <= m;k ++){
int i = id1[k];
while(nxt <= m && q[id2[nxt]] <= p[i]){
int j = id2[nxt ++];
// cout << j << '\n';
if(dp[j] == 1e18) continue;
int st = v[j];
while(Q[st].size() > 1 && slope(j, Q[st][Q[st].size() - 2]) <= slope(Q[st][Q[st].size() - 2], Q[st][Q[st].size() - 1])){
Q[st].pop_back();
}
Q[st].push_back(j);
}
int st = u[i];
if(Q[st].empty()) continue;
while(Q[st].size() > 1 && slope(Q[st][0], Q[st][1]) <= 2.0 * A * p[i]){
Q[st].pop_front();
}
int j = Q[st][0];
// cout << "i : " << i << ' ' << "j : " << j << '\n';
dp[i] = dp[j] + A * (p[i] - q[j]) * (p[i] - q[j]) + B * (p[i] - q[j]) + C;
}
ll ans = 1e18;
for(int i = 1;i <= m;i ++){
if(v[i] == n && dp[i] != 1e18){
ans = min(dp[i] + q[i], ans);
}
}
cout << ans << '\n';
return 0;
}