LOJ|LOJ 3156: 「NOI2019」回家路线
题目传送门:LOJ #3156。
题意简述:
【LOJ|LOJ 3156: 「NOI2019」回家路线】有一张 \(n\) 个点 \(m\) 条边的有向图,边有两个权值 \(p_i\) 和 \(q_i\)(\(p_i
假设路线依次经过的边为 \(\{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
因为不等号是大于号,所以维护下凸壳。
注意,为了方便,更新顺序为按照 \(p_i\) 从小到大,这样右侧斜率是递增的,但是并不能更新完立刻加入凸壳,而是应该等到轮到相应的 \(p_i\) 时再加入。
以下是代码,时间复杂度为 \(\mathcal{O}(n+m+\max q)\):
#include
转载于:https://www.cnblogs.com/PinkRabbit/p/NOI2019D1T1.html
推荐阅读
- 八、「料理风云」
- 「#1-颜龙武」区块链的价值是什么()
- 《深度倾听》第5天──「RIA学习力」便签输出第16期
- 「按键精灵安卓版」关于全分辨率脚本的一些理解(非游戏app)
- 「我的2017」——2017|「我的2017」——2017,大事件盘点
- 「适合发朋友圈的可爱短句文案」
- 「漫威之父」斯坦·李去世,回味老爷子在漫威中客串的各种角色
- 史前艺术的审美类型「清央美术」
- 「未来30年」你的孩子会成为社会精英吗()
- 「日记」他乡,温暖的日子