【区间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
",f[1][n]);
	}
	return 0;
}