求问这个 2D/0D 的区间 dp 如何优化
  • 板块学术版
  • 楼主LCATreap
  • 当前回复14
  • 已保存回复14
  • 发布时间2023/3/7 14:59
  • 上次更新2023/10/23 22:47:19
查看原帖
求问这个 2D/0D 的区间 dp 如何优化
727888
LCATreap楼主2023/3/7 14:59

rt，上午打的一个模拟赛的题，需要优化到 O(nlog⁡n)\mathcal O(n \log n) 或者 O(n)\mathcal O(n) 级别。

转移方程为：

f(l,r,k)={0if l=0∧r=0f(l,r+1,1)+(n−r+1)(sr−sx)if l=0f(l−1,r,0)+l(sx−sl)if r=0min⁡{f(l−1,r,0)+(n−r+l+1)(sx−sl), f(l,r+1,1)+(n−r+l+1)(sr−sx)}Ohterf(l,r,k) = \begin{cases} 0 & \text{if $l = 0 \wedge r = 0$} \\ f(l,r+1,1) + (n - r + 1)(s_r - s_x) & \text{if $l = 0$} \\ f(l-1,r,0) + l(s_x - s_l) & \text{if $r = 0$} \\ \min \lbrace f(l-1,r,0) + (n - r + l + 1)(s_x - s_l),\, f(l,r+1,1) + (n - r + l + 1)(s_r - s_x) \rbrace & \text{Ohter} \end{cases}

xx 的值为：

x={l+1if k=0r−1if k=1x = \begin{cases} l + 1 & \text{if $k = 0$} \\ r - 1 & \text{if $k = 1$} \end{cases}

其中 ss 是前缀和，mm 给定，nn 为某个序列的长度，序列中所有数都是正整数（所以 ss 单调递增），而要求的值为 f(m−1,m+1,0)f(m - 1,m + 1, 0) 或者 f(m−1,m+1,1)f(m - 1,m + 1, 1)。

求问一下是否存在一些优化方法，感谢！

2023/3/7 14:59