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： ```cpp #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有力的工具。