[HDU 3516]Tree Construction


Description

题库链接

给你 \(n\) 个偏序点对 \((x_i, y_i)\)(即 \(\forall i,j, x_i < x_j\) 时有 \(y_i > y_j\)),你需要在这一二维平面上画线,使得所有点连成一棵树,并且线只能从一个点开始向左或向下连。问最少需要画线的长度。

\(1\leq n\leq 1000\)

Solution

\(f_{l,r}\) 为将区间 \([l, r]\) 内的点连起来的最少长度。那么答案为 \(f_{1,n}\)

有转移方程 \(f_{l,r}=\min\{f_{l,k}+f_{k+1,r}+w(l, r)\}\),可以证明 \(w\) 是满足四边形不等式的。(考虑证明:\(w(i, j+1)-w(i, j)\geq w(i+1, j+1)-w(i+1, j)\))。

那么就可以用四边形不等式定理来优化这一 DP。

Code

#include 
#define pii pair
#define fr first
#define sc second
#define w(i, j) (a[k+1].fr-a[i].fr+a[k].sc-a[j].sc)
using namespace std;
const int N = 1005, inf = 2e9;

int f[N][N], n, s[N][N];
pii a[N];

int main() {
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; i++) scanf("%d%d", &a[i].fr, &a[i].sc);
        sort(a+1, a+n+1);
        for (int i = 1; i <= n; i++)
            for (int j = i+1; j <= n; j++)
                f[i][j] = inf;
        for (int i = 1; i <= n; i++) s[i][i] = i;
        for (int len = 2; len <= n; len++)
            for (int l = 1, r; (r = l+len-1) <= n; l++) {
                for (int k = s[l][r-1]; k <= s[l+1][r]; k++)
                    if (k < r && f[l][k]+f[k+1][r]+w(l, r) < f[l][r]) {
                        f[l][r] = f[l][k]+f[k+1][r]+w(l, r);
                        s[l][r] = k;
                    }
            }
        printf("%d\n", f[1][n]);
    }
    return 0;
}