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;

明显了吧

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

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdlib>

 #define N 1007

 #define M 500007

 #define inf 2000000009

 using namespace std;

 int n;

 int f[N][N],s[N][N];

 struct Node{int x,y;}a[M];

 int cost(int i,int j,int k)

 {

     if (k>=j) return inf;

     return a[k].y-a[j].y+a[k+].x-a[i].x;

 }

 int main()

 {

     while (~scanf("%d",&n))

     {

         for (int i=;i<=n;i++)

             scanf("%d%d",&a[i].x,&a[i].y);

         for (int i=;i<=n;i++)

             s[i][i]=i;

         memset(f,,sizeof f);

         for (int L=;L<=n;L++)

             for (int i=;i+L-<=n;i++)

              {

                 int j=L+i-;f[i][j]=inf;

                 for (int k=s[i][j-];k<=s[i+][j];k++)

                 {

                     int tmp=f[i][k]+f[k+][j]+cost(i,j,k);

                     if (tmp<f[i][j]) f[i][j]=tmp,s[i][j]=k;

                 }

             }

         printf("%d\n",f[][n]);

     }

 }

巴特西

hdu3516 Tree Construction (四边形不等式)

最新文章

热门文章