让菜鸡讲一讲四边形不等式优化

众所周知四边形不等式优化是应用在区间DP里面的我也不知道有什么其它地方可以用

那么我们有时候在做区间DP的时候可以遇见这样的转移方程

[f(i,j)=min(f(i,k-1),f(k,j))+w(i,j),ileq kleq j ]

f(i,j)表示的是在(i,j)上的最优值，而w(i,j)是转移所需额外的代价

众所周知这玩意儿复杂度是(O(n^3))的

看起来很不爽

那么现在我们可以用四边形不等式优化这个技能来把它优化一下

不过这个技能的使用是有条件的

四边形不等式优化条件

区间包含的单调性

额，其实就是对于每个(aleq b < cleq d)

满足(w(a,d)geq w(b,c))

就是某个区间的w不能小于它的子区间的w

四边形不等式

对于每个(aleq b < cleq d)

也满足(w(a,c)+w(b,d)leq w(a,d)+w(b,c))

      v-------v
  v-----------------v
oooooooooooooooooooooo
  ^-----------^
      ^-------------^

就是上面2个w加起来不能小于下面2个w

在满足了条件后

于是w函数满足区间包含的单调性和四边形不等式后

一个定理可以使用啦：f函数也相应的满足了四边形不等式

假设(f(i,j)=min(f(i,k-1),f(k,j))+w(i,j))在(k=loc(i,j))取到最小

因为f函数也满足了四边形不等式

所以loc函数是单调的，即(loc(i,j)leq loc(i,j+1)leq loc(i+1,j+1))

那么有一个强大的定理又可以使用了：

[f(i,j)=min(f(i,k-1),f(k,j))+w(i,j),loc(i,j-1)leq kleq loc(i+1,j) ]

至于有多强大？你可以发现这个转移的复杂度变成了(O(n^2))