社区讨论

关于 dp 优化

OOrientDragon
学术版参与者 4已保存回复 11

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
11 条
当前快照
1 份
快照标识符
@m5gpyf1d
此快照首次捕获于
2025/01/03 20:16
去年
此快照最后确认于
2025/11/04 23:17
4 个月前
查看原帖
fi=min⁡a≤j≤i{fj+⌊i−1j⌋+i−j}\displaystyle f_i=\min_{a \le j \le i}\{f_j+\lfloor\dfrac{i-1}{j}\rfloor+i-j\}
其中 aa 为给定常数。
这是一个 O(n2)\mathcal O(n^2) 的 dp，能否优化至 O(nlog⁡n)\mathcal O(n\log n)（或以下）？

回复

共 11 条回复，欢迎继续交流。

正在加载回复...