hdu 3516 Tree Construction 四邊形不等式優化

題目連結

題意：

二維坐标上，給出n個點，x嚴格單增，y嚴格單減。要求将這些點構成一棵樹，其中邊的方向隻能是x軸正向和y軸正向。問樹中所有邊的長度之和最短為多少。

分析:

因為規定了變得方向，是以根節點坐标應該不在第一個點右邊，也應該不在最後一個點上面。容易感覺到根節點一定就在（a[1].x,a[n].y）處。

dp[le][ri]=min{dp[le][k]+dp[k+1][ri]+a[k+1].x-a[le].x+a[k].y-a[ri].y}

這個題目的四邊形不等式不會證(從來就沒會過)。

下面證明在滿足四邊形不等式的前提下，決策滿足單調性：

令m[le,ri]=dp[le][ri]，該區間的決策k為s[le,ri]

有m[le,ri]=m[le,k]+m[k+1,ri]+a[k+1].x-a[le].x+a[k].y-a[ri].y

下面證明s[i,j-1]<=s[i,j]<=s[i+1,j]

先證明s[i,j]<=s[i+1,j]

設 d=s[i,j],設k<=d

則有 mk[i,j]>=md[i,j]

下面需要證明 mk[i+1,j]>=md[i+1,j]

引理： mk[i+1,j]−md[i+1,j]>=mk[i,j]−md[i,j]

由引理知

mk[i+1,j]−md[i+1,j]>=mk[i,j]−md[i,j]>=0

故 mk[i+1,j]>=md[i+1,j]， 即[i+1,j]的決策點絕不會在[i,j]決策點左邊。

證畢。

關于引理的證明：

mk[i+1,j]−md[i+1,j]>=mk[i,j]−md[i,j]>=0

左邊=mk[i+1,j]−md[i+1,j]

=m[i+1,k]+m[k+1,j]+a[k].y−a[j].y+a[k+1].x−a[i].x−

(m[i+1,d]+m[d+1,j]+a[d].y−a[j].y+a[d+1].x−a[i]x)

=m[i+1,k]+m[k+1,j]+a[k].y+a[k+1].x−

(m[i+1,d]+m[d+1,j]+a[d].y+a[d+1].x)

<script type="math/tex; mode=display" id="MathJax-Element-100"></script>

同理右邊=m[i,k]+m[k+1,j]+a[k].y+a[k+1].x−

(m[i,d]+m[d+1,j]+a[d].y+a[d+1].x)

是以待證式子等價于

m[i+1,k]−m[i+1,d]>=m[i,k]−m[i,d] (消去，化簡)

即

m[i+1,k]+m[i,d]>=m[i,k]+m[i+1,d]

因為k∈[i+1,j] (這是因為考慮[i+1,j]内的決策點), 是以

i<i+1<=k<=d ,滿足四邊形不等式的條件，是以

m[i+1,k]+m[i,d]>=m[i,k]+m[i+1,d],引理證畢。

代碼：

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define for1(a, n) for (int (a) = 1; (a) <= (n); (a)++)
#define ysk(x)  (1<<(x))
const int INF =;
const int maxn=   ;
int n,s[maxn+][maxn+],dp[maxn+][maxn+];
struct Node
{
    int x,y;
}a[maxn+];

int main()
{
   std::ios::sync_with_stdio(false);
   while(cin>>n)
   {
       for1(i,n)  cin>>a[i].x>>a[i].y;

       for1(i,n)
       {
           dp[i][i]=;
           s[i][i]=i;
       }

       for(int add=;add<n;add++)
       {
           for(int le=;le+add<=n;le++)
           {
               int ri=le+add;
               int L=s[le][ri-];
               int R=s[le+][ri];
               dp[le][ri]=INF;
               for(int k=L;k<=R&&k<ri;k++)
               {
                   int ret=dp[le][k]+dp[k+][ri]+a[k+].x-a[le].x+a[k].y-a[ri].y;
                   if(ret<=dp[le][ri])
                   {
                      dp[le][ri]=ret;
                      s[le][ri]=k;
                   }
               }

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

   }
   return ;
}