2013-team6/dp

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

http://www.notonlysuccess.com/index.php/dp_optimize/

=== 四边形不等式 ===

dp[i][j] = min { dp[i][k] + dp[k+1][j] } + w(i,j)

1: 判断 是否满足 w(i,j) + w(i+1,j+1) <= w(i,j+1) + w(i+1,j) (凸函数)

2: 判断 是否满足 w(i+1,j) <= w(i,j+1)                      （区间单调关系）

3: 若满足1与2， 则 s[i][j-1] <= s[i][j] <= s[i+1][j] , s[i][j] 为 dp[i][j]的最优决策

复杂度 O(n^2 )

----

=== 斜率优化 ===

dp[i] = min { dp[j] } + a[i] * b[j] + F(i)

转化为 G = y[i] + a[i] * x[i]  ( y[i] = dp[j] , x[i] = b[j] )

维护一个下凸的序列

1) a[i], x[i] 均单调 ， 单调队列维护 ，对于每一个步:

    1： 判断 G(q[qh]) > G(q[qh+1]) , 队头出队

    2： dp[i] = G(q[qh]]) + F(i)

    3: 将 i 加入队尾， 判断队列中最后3个点是否下凸 ， 注意a[i] , x[i] 的单调性 

    复杂度O(n^2 )

2）a[i], x[i] 至少一个不单调   平衡术维护 

http://www.notonlysuccess.com/index.php/dp_optimize/

四边形不等式

dp[i][j] = min { dp[i][k] + dp[k+1][j] } + w(i,j)

1: 判断 是否满足 w(i,j) + w(i+1,j+1) <= w(i,j+1) + w(i+1,j) (凸函数)

2: 判断 是否满足 w(i+1,j) <= w(i,j+1) （区间单调关系）

3: 若满足1与2， 则 s[i][j-1] <= s[i][j] <= s[i+1][j] , s[i][j] 为 dp[i][j]的最优决策

复杂度 O(n^2 )

---

斜率优化

dp[i] = min { dp[j] } + a[i] * b[j] + F(i)

转化为 G = y[i] + a[i] * x[i] ( y[i] = dp[j] , x[i] = b[j] )

维护一个下凸的序列

1) a[i], x[i] 均单调 ， 单调队列维护 ，对于每一个步:

1： 判断 G(q[qh]) > G(q[qh+1]) , 队头出队

2： dp[i] = G(q[qh]]) + F(i)

3: 将 i 加入队尾， 判断队列中最后3个点是否下凸 ， 注意a[i] , x[i] 的单调性

复杂度O(n^2 )

2）a[i], x[i] 至少一个不单调 平衡术维护