关于单调队列优化dp
  • 板块学术版
  • 楼主Eous
  • 当前回复2
  • 已保存回复2
  • 发布时间2025/1/10 14:29
  • 上次更新2025/1/10 20:44:45
查看原帖
关于单调队列优化dp
549131
Eous楼主2025/1/10 14:29

假如有个 dp 方程:

dpi,j=mink=0i{dpk,j1+something}dp_{i,j} = \min\limits_{k = 0}^{i}\{dp_{k,j - 1} + \text{something}\}

最外层循环 jj。那么对于一个 jj,它这一列通过单调队列转移完了,然后我循环到下一个 jj,单调队列要清空吗?

你只用回答上面的问题。如果情况依题目和写法而定,请看题目链接代码

2025/1/10 14:29
加载中...