【区间dp】【四边形不等式】CDOJ1653 最小生成树？

四边形不等式优化的资料去网上找下吧！很多。

可以证明，这个题里面，合并的代价满足较小区间+较大区间<=交错区间。

可以自己画个图看看。

#include<cstdio>
#include<algorithm>
using namespace std;
struct Point{
int x,y;
}p[1010];
bool cmp(const Point &a,const Point &b){
return a.x!=b.x ? a.x<b.x : a.y>b.y;
}
int n,f[1010][1010],K[1010][1010];
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;++i){
scanf("%d%d",&p[i].x,&p[i].y);
}
sort(p+1,p+n+1,cmp);
for(int i=1;i<=n;++i){
for(int j=i;j<=n;++j){
f[i][j]=2000000000;
}
}
for(int i=1;i<=n;++i){
f[i][i]=0;
K[i][i]=i;
}
for(int i=2;i<=n;++i){
for(int l=1;l+i-1<=n;++l){
int r=l+i-1;
for(int k=K[l][r-1];k<=K[l+1][r];++k){
if(k!=r){
if(f[l][k]+f[k+1][r]+p[k+1].x-p[l].x+p[k].y-p[r].y<f[l][r]){
f[l][r]=f[l][k]+f[k+1][r]+p[k+1].x-p[l].x+p[k].y-p[r].y;
K[l][r]=k;
}
}
}
}
}
printf("%d\n",f[1][n]);
}
return 0;
}