求问决策单调性优化dp
  • 板块灌水区
  • 楼主zzy_zzy
  • 当前回复10
  • 已保存回复10
  • 发布时间2025/2/6 10:33
  • 上次更新2025/2/6 13:49:05
查看原帖
求问决策单调性优化dp
760776
zzy_zzy楼主2025/2/6 10:33

如果在做dp题时:遇到以下转移式子:

dpi=min(dpj+calc(i,j))dp_i=\min{(dp_j+calc(i,j))}

假设通过打表发现它有决策单调性。在进行优化时,要获取 mid 的决策点。如果要获取 mid 的决策点,就要获得 l 至 mid-1 的dp值,可现在我们并不知道其dp值,应该怎么办

2025/2/6 10:33
加载中...