社区讨论

关于四边形不等式的一个疑问

学术版参与者 2已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@m5i89jfq
此快照首次捕获于
2025/01/04 21:36
去年
此快照最后确认于
2025/11/04 11:58
4 个月前
查看原帖
若函数 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 吗?

回复

2 条回复,欢迎继续交流。

正在加载回复...