网站首页
编程语言
数据库
系统相关
其他分享
编程问答
斜优
2024-09-28
斜优小记
一个启发是,对于一个\(i\)的两个转移\(j,k\),比较\(j\)与\(k\)的转移优劣。可以用斜率优化的场景:对比后可以分拆出\(slope(j,k)\le\texttt{只和i相关的一些东西}\)的形式。例如P3195,首先写出转移方程\(dp_i=\min\limits_{0\lej<i}\{dp_j+(s_i-s_j+i-j-1-L)^2\}\)比