原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=3516

题意：

大概就是给你个下凸包的左侧，然后让你用平行于坐标轴的线段构造一棵树，并且这棵树的总曼哈顿距离最短

题解：

很容易得到转移方程：

$$dp[i][j]=min \{ dp[i][k-1]+dp[k][j] + dis(uni(i,k-1),uni(k,j))\}$$

其中$dp[i][j]$表示从$i$到$j$的最优解，$dis(i,j)$表示$i$和$j$之间的曼哈顿距离，$uni(i,j)$表示将$i$和$j$用平行于坐标轴的线段连在一起时的拐角点。

然后可以证明这是满足四边形优化条件的。

然后四边形优化一下就好。

代码：

#include<iostream>

#include<cstring>

#include<queue>

#include<vector>

#include<algorithm>

#include<climits>

#include<cmath>

#define MAX_N 1234

#define INF LLONG_MAX/1234

using namespace std;

typedef long long LL;

LL dp[MAX_N][MAX_N];

int n;

struct point {

public:

    LL x, y;

    point(LL xx, LL yy) : x(xx), y(yy) { }

    point() { }

};

point P[MAX_N];

LL dis(point a,point b){

    return abs(a.x-b.x)+abs(a.y-b.y);

}

point uni(point a,point b) {

    return point(min(a.x, b.x), min(a.y, b.y));

}

int s[MAX_N][MAX_N];

int main() {

    cin.sync_with_stdio(false);

    while (cin >> n) {

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

            cin >> P[i].x >> P[i].y;

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

            for (int j = ; j <= n; j++) {

                if (i == j)

                    dp[i][j] = ;

                else

                    dp[i][j] = INF;

            }

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

            dp[i][i + ] = dis(P[i], P[i + ]), s[i][i + ] = i + ;

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

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

                int j = i + t;

                int pos = ;

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

                    if (dp[i][j] > dp[i][k - ] + dp[k][j]+ dis(uni(P[i], P[k - ]), uni(P[k], P[j])))

                        dp[i][j] = dp[i][k - ] + dp[k][j] + dis(uni(P[i], P[k - ]), uni(P[k], P[j])), pos = k;

                s[i][j] = pos;

            }

        cout << dp[][n] << endl;

    }

    return ;

}

巴特西

HDOJ 3516 Tree Construction 四边形优化dp

题意：

题解：

代码：

最新文章

热门文章