wqs二分是否能优化分治决策单调性dp
  • 板块学术版
  • 楼主williamwei
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/7 15:53
  • 上次更新2024/12/7 18:10:41
查看原帖
wqs二分是否能优化分治决策单调性dp
700558
williamwei楼主2024/12/7 15:53

rt.

已知条件：f(m)f(m)为下凸函数，存在决策单调性，但贡献不好求，需要使用分治优化

优化目的：O(nklog⁡n)→O(nlog⁡nlog⁡V)\mathcal{O}(nk \log n) \to \mathcal{O}(n \log n \log V)

2024/12/7 15:53