主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
P4655 [CEOI2017] Building Bridges
最后更新于 2025-08-28 09:13:24
作者
2huk
分类
题解
题解
P4655
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
快进到 DP 式子： $$ \begin{aligned} f(i) &= \min \{f(j) + (h_i - h_j)^2 + s_{i-1}-s_j\} \\ &= \min \{f(j) + h_i^2 + h_j^2 - 2h_ih_j + s_{i-1} - s_j\} \\ &= \min \{-2h_ih_j + f(j) + h_j^2 - s_j\} + h_i^2 + s_{i-1} \\ \end{aligned} $$ 视 $-2h_j = y$，$f(j) + h_j^2 - s_j = b$，那么前面的 $\min$ 等价于求当 $x = h_i$ 时直线 $y = kx+b$ 的最小值。李超树即可。
正在渲染内容...
点赞
1
收藏
0
