DP优化（三）四边形不等式优化实例讲解

有一种DP可以写成四边形不等式，那么可以用一个优化来优化这种DP（一般是二维的，不加优化是O(n3)）。

如果a≤b≤c≤d，那么如果DP式子满足f(a,c)+f(b,d)≤f(b,c)+f(a,d)，那么这就是一个四边形不等式。

一、首先先看一道例题

题目：有一群人要乘船, 一共有k条船, 现在要将n个排好堆的人分进这k条船中, 使得总代价尽可能小

上船的方法如下:

首先第一条船靠岸, 队伍中前q1个人上船

然后第二条船靠岸, 队伍中前q2个人上船

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

最后第kk条船靠岸, 队伍中qk个人上船

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

设第i到第j个人乘坐了一条船, 则定义这一条船的代价为cost(k,t)其中cost数组已知

定义一种乘船方法的代价为, 每一条船的代价之和

求最小可能代价

解题：首先不难想到这道题可以使用dp

令dp(i,j)dp(i,j)表示当前考虑了前ii个人, 一共使用了jj条船的最小代价

转移十分明显：其中 w(i,j) 表示从第 i 个人到第 j 个人坐在一条船上的代价；

但是, 我们发现这样做复杂度为, 显然会超时

这时候我们就要优化它

优化，肯定是想减去一些无用的转移

例如，一共10个人,要坐5艘船, 让每艘船坐2个人, 感觉上就比前4艘船每艘坐1个人, 最后一艘船挤满人要优得多

这时候我们就要用到四边不等式优化dp

二、四边形不等式

如果有一个矩阵M，对于任意a<b,c<d，有M(a,c)+M(b,d)≥M(a,d)+M(b,c)，我们就称这个矩阵满足四边形不等式

我们考虑一个简单的问题：如何验证一个矩阵是否满足四边形不等式？

显然有的算法，但事实上我们可以依靠下面的性质在O(nm)的复杂度内判断：

∀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列内的所有等式左边相加，右边相加，抵消一下，右边就能推到左边。

三、决策单调性

对于一个矩阵MM，如果对于任意a<b,c<d，如果M(a,c)≥M(a,d)，也满足M(b,c)≥M(b,d)，就称这个矩阵具有完全单调性。

事实上，假如一个矩阵满足四边形不等式，它就满足决策单调性。

证明：我们考虑反证法

假如∃a<b,c<d，满足M(a,c)≥M(a,d),M(b,c)<M(b,d)，

我们可以发现M(a,d)+M(b,c)<M(a,c)+M(b,d)，与四边形不等式矛盾