hdu3516 Tree Construction (四边形不等式)

题意：给定一些点(xi,yi)(xj,yj)满足:i<j,xi<xj,yi>yj。用下面的连起来，使得所有边的长度最小？

题解：直接给出吧

f[i][j]=min(f[i][k]+f[k+1][j]+cost(i,j)

cost(i,j)=a[k].y-a[j].y+a[k+1].x-a[i].x;

明显了吧

证明一下，搞一搞，四边形性质就出来了，模板题吧。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #define N 1007
 8 #define M 500007
 9 #define inf 2000000009
10 using namespace std;
11 
12 int n;
13 int f[N][N],s[N][N];
14 struct Node{int x,y;}a[M];
15 
16 int cost(int i,int j,int k)
17 {
18     if (k>=j) return inf; 
19     return a[k].y-a[j].y+a[k+1].x-a[i].x;
20 }
21 int main()
22 {
23     while (~scanf("%d",&n))
24     {
25         for (int i=1;i<=n;i++)
26             scanf("%d%d",&a[i].x,&a[i].y);
27         for (int i=1;i<=n;i++)
28             s[i][i]=i;
29         memset(f,0,sizeof f);
30         for (int L=2;L<=n;L++)
31             for (int i=1;i+L-1<=n;i++)
32              {
33                 int j=L+i-1;f[i][j]=inf;
34                 for (int k=s[i][j-1];k<=s[i+1][j];k++)
35                 {
36                     int tmp=f[i][k]+f[k+1][j]+cost(i,j,k);
37                     if (tmp<f[i][j]) f[i][j]=tmp,s[i][j]=k;
38                 }
39             }
40         printf("%d
",f[1][n]); 
41     }
42 }