有一種DP可以寫成四邊形不等式，那么可以用一個(gè)優(yōu)化來優(yōu)化這種DP（一般是二維的，不加優(yōu)化是O(n3)）。

如果a≤b≤c≤d，那么如果DP式子滿足f(a,c)+f(b,d)≤f(b,c)+f(a,d)，那么這就是一個(gè)四邊形不等式。

一、首先先看一道例題

題目：有一群人要乘船, 一共有k條船, 現(xiàn)在要將n個(gè)排好堆的人分進(jìn)這k條船中, 使得總代價(jià)盡可能小

上船的方法如下:

首先第一條船靠岸, 隊(duì)伍中前q1個(gè)人上船

然后第二條船靠岸, 隊(duì)伍中前q2個(gè)人上船

............

最后第kk條船靠岸, 隊(duì)伍中qk個(gè)人上船

為了保證所有人都有船坐, 要求 q1+q2+...+qk=n 并且 q1,q2,...,qk>0

設(shè)第i到第j個(gè)人乘坐了一條船, 則定義這一條船的代價(jià)為cost(k,t)其中cost數(shù)組已知

定義一種乘船方法的代價(jià)為, 每一條船的代價(jià)之和

求最小可能代價(jià)

解題：首先不難想到這道題可以使用dp

令dp(i,j)dp(i,j)表示當(dāng)前考慮了前ii個(gè)人, 一共使用了jj條船的最小代價(jià)

轉(zhuǎn)移十分明顯：其中 w(i,j) 表示從第 i 個(gè)人到第 j 個(gè)人坐在一條船上的代價(jià)；

但是, 我們發(fā)現(xiàn)這樣做復(fù)雜度為, 顯然會(huì)超時(shí)

這時(shí)候我們就要優(yōu)化它

優(yōu)化，肯定是想減去一些無用的轉(zhuǎn)移

例如，一共10個(gè)人,要坐5艘船, 讓每艘船坐2個(gè)人, 感覺上就比前4艘船每艘坐1個(gè)人, 最后一艘船擠滿人要優(yōu)得多

這時(shí)候我們就要用到四邊不等式優(yōu)化dp

二、四邊形不等式

如果有一個(gè)矩陣M，對(duì)于任意a<b,c<d，有M(a,c)+M(b,d)≥M(a,d)+M(b,c)，我們就稱這個(gè)矩陣滿足四邊形不等式

我們考慮一個(gè)簡單的問題：如何驗(yàn)證一個(gè)矩陣是否滿足四邊形不等式？

顯然有的算法，但事實(shí)上我們可以依靠下面的性質(zhì)在O(nm)的復(fù)雜度內(nèi)判斷：

?a<b,c<d，M(a,c)+M(b,d)≥M(a,d)+M(b,c)

??1≤a≤n?1，1≤b≤m?1，M(a,b+1)+M(a+1,b)≥M(a,b)+M(a+1,b+1)

從左邊推到右邊是顯然的，只要令a=a,b=a+1,c=b,d=b+1就好

從右邊推到左邊，我們可以把第a行到第b行，第c列到第d列內(nèi)的所有等式左邊相加，右邊相加，抵消一下，右邊就能推到左邊。

三、決策單調(diào)性

對(duì)于一個(gè)矩陣MM，如果對(duì)于任意a<b,c<d，如果M(a,c)≥M(a,d)，也滿足M(b,c)≥M(b,d)，就稱這個(gè)矩陣具有完全單調(diào)性。

事實(shí)上，假如一個(gè)矩陣滿足四邊形不等式，它就滿足決策單調(diào)性。

證明：我們考慮反證法

假如?a<b,c<d，滿足M(a,c)≥M(a,d),M(b,c)<M(b,d)，

我們可以發(fā)現(xiàn)M(a,d)+M(b,c)<M(a,c)+M(b,d)，與四邊形不等式矛盾