题目大意：在一个一维坐标轴上有v个(1<=v<=300)村庄，要建p(1<=p<=30)个邮局，每个村庄都到最近的邮局，要求最小的距离和。
四边形不等式，据说黑书上写得很高深。
描述是这样的：令(a<=b<=c<=d，i<=k<j)，若w[a][c]+w[b][d]<=w[a][d]+w[b][c]，m[i][j]=min OR max{m[i][k]+m[k+1][j]+w[i][j]}则m[a][c]+m[b][d]<=m[a][d]+m[b][c]。
对于这个式子，个人觉得没必要深究，读者读读题目就应该知道自己要求的m[i][j]定义，取min或者max。我也不会证明，只能弱弱感受到是这么回事。（毕竟那些都不重要，因为不涉及最后求解结果）
最重要的是这个式子，假设s[i][j]是对应取到m[i][j]的最优解（s当然是solution的意思了，关于解的描述要细细考虑，因为它并不用是一种很确切的表示，只需要是一个关键的量就可以）。PS：我觉得，我要是不解释这个关键量，很多人肯定会黑我的，但是我真的不知道怎么表达。看代码中的注解吧。
四边形不等式最大优化是s[i][j]一定介于s[k=i-1 或者 k=i+1][j]、s[i][j+1]之间。（也有很多博客上写成s[i-1][j]<=s[i][j]<=s[i][j+1]）这样对于我们搜索关于s[i][j]的值时范围大大缩短了。对于s[i][max_(i)]可以用我们通常容易想到的dp方程线性效率解决。而s[i][1]到s[i][max_(i)-1]这一段的解，总共的效率可以缩短到线性。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int infinity=(-)^(<<);
const int V=;
const int P=;
int dp[V][P], s[V][P];
int atx[V],sum[V];
inline int setat(int i,int j){
return (i+j)>>;
}
int move_all(int fr,int ba){
//printf("move from %d to %d = %d\n",fr,ba,(sum[ba]-sum[fr])-atx[fr]*(ba-fr));
return (sum[ba]-sum[fr])-atx[fr]*(ba-fr);
}
int S(int i,int j){
int pos=setat(i,j);
int ret=move_all(pos,j);
ret += (atx[pos]-atx[i])*(pos-i+)-move_all(i,pos);
return ret;
}
int DP(int v,int p){
sort(atx+,atx++v);
for(int i=v;i>=;i--) atx[i]-=atx[];
for(int i=;i<=v;i++) sum[i]=sum[i-]+atx[i];
//for(int i=1;i<=v;i++) printf("%3d ",atx[i]); printf("\n");
for(int i=;i<=v;i++)
dp[i][]=S(,i), s[i][]=setat(,i); //printf("1 --> %4d, %d\n",i,dp[i][1]);
if(p >= )
for(int i=;i<=v;i++){
int maxj=min(i,p);
dp[i][maxj]=infinity;
for(int k=maxj-;k<i;k++)
if(dp[k][maxj-]+S(k+,i) < dp[i][maxj])
dp[i][maxj]=dp[k][maxj-]+S(k+,i), s[i][maxj]=k;
//printf("dp[%d][%d] = %d, s[i][maxj] = %d\n",i,maxj,dp[i][maxj],s[i][maxj]);
for(int j=maxj-;j>=;j--){
dp[i][j]=infinity;
for(int k=s[i-][j];k<=s[i][j+];k++)
if(dp[k][j-]+S(k+,i) < dp[i][j]){
dp[i][j]=dp[k][j-]+S(k+,i);
s[i][j]=k;
}
}
}
return dp[v][p];
}
int main()
{
int v,p;
while(scanf("%d%d",&v,&p) != EOF){
for(int i=;i<=v;i++)
scanf("%d",&atx[i]);
printf("%d\n",DP(v,p));
}
return ;
}
个人觉得，在很多性质上，它跟斜率优化dp很像，甚至可以说斜率优化dp是最特殊的一类四边形不等式dp。斜率优化的dp中，最优化只根一个值有关，因为它保持后来无关单调。四边形不等式，把最优解的可选方案限制起来。
我也是四边形不等式的初学者，希望路过的大牛不吝赐教。