关于一类dp式子的优化
  • 板块灌水区
  • 楼主晴空一鹤
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/9/13 15:34
  • 上次更新2024/9/13 19:21:02
查看原帖
关于一类dp式子的优化
158400
晴空一鹤楼主2024/9/13 15:34

RT，首先给出一棵 11 到 nn 的树，然后有以下转移式：

dpi=max⁡j<i(dpj+ai×blca(i,j))+cidp_i= \max_{j<i} (dp_j+a_i\times b_{lca(i,j)})+c_i

这个可以优化至 nlog⁡nn\log n 吗/yiw

2024/9/13 15:34