LOJ 3156: 「NOI2019」回家路线
题目传送门: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}})\),化简式子:
\]
其中斜率的表达式是显然的,\(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\) 优当且仅当:
\]
因为不等号是大于号,所以维护下凸壳。
注意,为了方便,更新顺序为按照 \(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;
}
最新文章
- 简单的cookie使用
- css问题 ie7兼容性问题
- [Linq Expression]练习自己写绑定
- Uber新功能:隐藏司机乘客们的手机号码
- SolrEntityProcessor
- 纯代码添加约束条件(Auto Layout)
- SharePoint代码段设计
- Swift String length property
- docker学习笔记(一)-vagrant/docker machine安装docker,阿里云通过docker machine安装docker
- PHP设计模式_工厂模式
- JAVA核心技术I---JAVA基础知识(文本文件读写)
- 关于字符串 --java
- assembly.xml
- NIO的通道和缓冲区
- Ubuntu启动时a start job is running for dev-disk-by延时解决
- 比特币系列钱包的UTXO总结
- Java访问权限控制
- sys目录下常用文件汇总
- 【漏洞预警】Apache ActiveMQ Fileserver远程代码执行漏洞(CVE-2016-3088)
- C# 五大修饰符