coreBugZJ

此 blog 已弃。

四边形不等式

        四边形不等式用于 DP 优化。

状态转移方程
        d[ i, j ] = min{ d[ i, k - 1 ] + d[ k + 1 ][ j ] } + w[ i , j ]           i <= k <= j
时间复杂度为 O( n * n * n )。


        如果函数 w 满足: w[ a, c ] + w[ b, d ] <= w[ b, c ] + w[ a, d  ]               a < b < c < d
则说 w 满足凸四边形不等式(简称 w 为凸)。
        如果函数 w 满足:w[ i, j ] <= w[ i", j" ]                 [ i, j ] 包含于 [ i", j" ]
则说 w 关于区间包含关系单调。


定理一:
        如果 w 同时满足四边形不等式和区间单调关系,则 d 也满足四边形不等式;

定理二:
        定理一的条件满足时让 d[ i, j ] 取最小值的 k 为 K[ i, j ],则 K[ i, j - 1 ] <= K[ i, j ] <= K[ i + 1, j ];

定理三:
        w 为凸当且仅当 w[ i, j ] + w[ i + 1, j + 1 ] <= w[ i + 1, j ] + w[ i, j + 1 ]。


这样每次决策范围变成 K[ i + 1, j ] 到 K[ i, j - 1 ]。
按 j - i 递减的顺序递推各个状态值,则对于每个确定的 j - i 来说,决策总量为 O( n ),故总的时间复杂度为 O( n*n )。

————lrj 黑书


题目:

POJ    1160  Post Office

HDOJ  3480 Division


等等。。。

posted on 2011-03-18 10:09 coreBugZJ 阅读(1571) 评论(0)  编辑 收藏 引用 所属分类: Algorithm


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理