Tree Construct 四边形不等式

· · 个人记录

题目大意

给定平面上 n 个点 (x_i,y_i)，满足 x_i 单调递增， y_i 单调递减。求一棵最小生成树，连边方向只能按 x 轴 y 轴方向。

题解报告

设 f[i][j] 表示将 i\rightarrow j 这几个点联通的最小生成树边权和，就有以下的转移：f[i][j]=min\{f[i][k]+f[k+1][j]+(x[k+1]-x[i]+y[k]-y[j])\}

直接枚举左右端点和中间点转移，复杂度 O(n^3)

我们可以用四边形不等式优化，一般地，若转移方程 f[i][j]=max/min\{f[i][k]+f[k+1][j]+w[i][j]\}

满足 \forall i,i',j,j',i\leq i'\leq 'j \leq j 有

1.w(i,j)\geq w(i',j')

2. w(i,j)+w(i',j')\geq w(i,j')+w(i',j)

那么dp的决策点 s[i][j] 满足 s[i][j-1]\leq s[i][j]\leq s[i+1][j]

好的，我们猜想，我们的转移方程也满足上述四边形不等式的性质。经过实践，是正确的，所以我们记下每次的决策点进行转移，复杂度 O(n^2)

code below：

#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=0x3f3f3f3f;
const int maxn=1000;
int n,s[maxn+10][maxn+10],dp[maxn+10][maxn+10];
struct Node{int x,y;}a[maxn+10];
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]=0,s[i][i]=i;
       for(int add=1;add<n;add++){
           for(int le=1;le+add<=n;le++){
               int ri=le+add;
               int L=s[le][ri-1];
               int R=s[le+1][ri];
               dp[le][ri]=INF;
               for(int k=L;k<=R&&k<ri;k++){
                   int ret=dp[le][k]+dp[k+1][ri]+a[k+1].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[1][n]);
   }
   return 0;
}

写在最后

这种方法的证明非常困难，所以在OI中一般都是拿来直接试试看，就算不行，也可以用来骗分，是一种“优化”dp有力的工具。