CF1715E 题解
题意
一个带边权无向图,可以沿着边走,需要边权的花费或从任意点 \(u\) 飞到 \(v\),需要 \((u-v)^2\) 的花费。求从点 \(1\) 到所有 \(i\) 的最少花费。最多飞 \(k\) 次。
分析
一眼最短路 + dp。
发现 \(k\) 很小,可以枚举飞的次数,对于点 \(u\),可以是走到 \(u\),这种情况可以用最短路更新答案;也可以是飞到 \(u\),此时可以 dp,\(dp_i\) 表示从 \(1\) 到 \(i\) 最小花费,转移方程很显然:
\[dp_i=\min\limits_{t=1}^n(dis_t+(i-t)^2) \],其中 \(dis_i\) 表示上个 \(k\) 算出的 \(1\) 到 \(i\) 最少花费。此时最外层循环 \(k\),中层循环 \(i\),内层循环 \(t\),时间复杂度 \(\mathcal{O}(kn^2)\),发现会 T,考虑优化。
发现这个式子是个典型的斜率优化形式,可以变形成:
\[dp_i=\min\limits_{t=1}^n(dis_t+(i-t)^2) \\ \ \ \ \ \ \ \ \ \ \ \ \ =\min\limits_{t=1}^n(dis_t+t^2+it)+i^2 \]也就转化成了求 \(x=i\) 时所有直线 \(y=tx+(dis_t+t^2)\) 的最小值加上 \(i^2\) 的值。可以用李超线段树方便地求出。