关于四边形不等式的一个疑问
  • 板块学术版
  • 楼主TimSwn090306
  • 当前回复2
  • 已保存回复2
  • 发布时间2025/1/4 21:34
  • 上次更新2025/1/5 09:43:23
查看原帖
关于四边形不等式的一个疑问
564732
TimSwn090306楼主2025/1/4 21:34

若函数 val(i,j)val(i,j) 满足 val(a,d)+val(b,c)val(a,c)+val(b,d)val(a,d)+val(b,c)\ge val(a,c)+val(b,d),则形如 fi=maxj<i{fj+val(j,i)}f_i=\max_{j<i}\{f_j+val(j,i)\} 的 dp 有什么优良性质吗?

或者说对于一般的四边形不等式推导决策单调性的dp,把价值函数替换成任意时刻都不满足四边形不等式的价值函数,那么还能用一些奇妙手段优化这个 dp 吗?

2025/1/4 21:34
加载中...