P5468 [NOI2019]回家路线 [斜率优化dp] 回家路线回家路线回家路线
法
设 表示使用编号为 的边走到 节点的最小花费, 则
使用类似 的方法转移, 鉴于空间复杂度为 的, 只有.
代码 .
分
时间的范围很小, 考虑以枚举时刻进行 ,
设 表示时刻 走过 边的最小花费, 时间复杂度 , ( 为最大时间) 能过 .
理论上不能 , 所以要优化 .
每个边 出发/到达时刻 都是确定的, 于是可以建一个 时间队列,
预先在对应时刻插入边, 枚举时间时, 到了对应时刻, 再将边取出参加转移.
省掉第二维.
则设 表示 走完编号为 的边的最小花费, 则
去掉 化简, 仅关于决策的项放在一左边, 剩下的放在右边,
为 的形式,
- 因为求的是最小值, 所以维护 下凸壳;
- 因为 单调递增, 所以可以弹出队首 .
斜率优化 得到 时间复杂度.
没学过斜率优化的可以点击 这里 .
分
-
对每个点建单调队列, 所有到达该点的边都可以作为 从这条边出发的边 转移的来源,
每条边更新后都需要加入其终点对应时刻的 候选单调队列 , 在对应时刻取出加入正式队列, 以便后面的边进行更新. -
注意开始时, 节点的单调队列需要推入 元素, 使得 出发的边得到转移 .
-
转移时需判断决策来源是否为空, 即判断 指定边 的 出发点 的单调队列是否为空 .
转移时对每个点建单调队列保证了空间的来源正确, 遍历时间保证了时间的来源正确 .
#include<cstdio>
#include<vector>
#include<queue>
#define pb push_back
#define reg register
const int maxn = 2e5 + 10;
int N;
int M;
int A;
int B;
int C;
int Max_time;
int F[maxn];
struct Edge{ int x, y, p, q; } E[maxn];
double X(int i){ return E[i].q; }
double Y(int i){ return F[i] + A*E[i].q*E[i].q - B*E[i].q; }
double slope(int x, int y){ return (Y(x) - Y(y)) / (X(x) - X(y)); }
std::deque <int> Q[100005];
std::vector <int> Time_line[3005];
std::vector <int> Get_off[3005];
int main(){
scanf("%d%d%d%d%d", &N, &M, &A, &B, &C);
for(reg int i = 1; i <= M; i ++){
scanf("%d%d%d%d", &E[i].x, &E[i].y, &E[i].p, &E[i].q);
Max_time = std::max(Max_time, E[i].p);
Time_line[E[i].p].pb(i);
}
int Ans = 0x7f7f7f7f;
Q[1].pb(0);
for(reg int tim = 0; tim <= Max_time; tim ++){
int size = Get_off[tim].size();
for(reg int j = 0; j < size; j ++){
int id = Get_off[tim][j];
int t1 = E[id].y;
while(Q[t1].size() >= 2 && slope(Q[t1][Q[t1].size()-1], Q[t1][Q[t1].size()-2]) >= slope(Q[t1][Q[t1].size()-2], id))
Q[t1].pop_back();
Q[t1].push_back(id);
}
size = Time_line[tim].size();
for(reg int k = 0; k < size; k ++){
int j = Time_line[tim][k];
int t1 = E[j].x;
if(Q[t1].size() == 0) continue ;
double K = 2*A*E[j].p;
while(Q[t1].size() >= 2 && slope(Q[t1][0], Q[t1][1]) < K) Q[t1].pop_front();
int i = Q[t1].front();
F[j] = F[i] + A*(E[j].p-E[i].q)*(E[j].p-E[i].q) + B*(E[j].p - E[i].q) + C;
Get_off[E[j].q].pb(j);
if(E[j].y == N) Ans = std::min(Ans, F[j]+E[j].q);
}
}
printf("%d
", Ans);
return 0;
}