HDU 5473 There was a kingdom 凸包 DP

题意:

给出平面上n个点的坐标,选k个点,使得这k个点围起来的面积最大.

分析:

参考了叉姐的分析和不慌不忙菊苣的代码

思路我都懂,但是DP的部分还是不太会写.

我体会了一下其中含义,也许这样可能会好理解一点:

因为求出来的凸包的点数是固定的,所能选的点数也是固定的,那么不选的点的数量也是固定的.

可以反过来考虑:少选一个点,就要损失凸包上的一块面积.

假设\(d(i,j)\)表示考虑了前\(i\)个点,选了\(j\)个点,所损失的最少面积.

第\(i\)个点的前一个点是\(i'\),损失的面积为\(S_{cut}\),那么\(d(i,j)=min(d(i,j),d(i',j-1)+S_{cut})\)

最后答案就是凸包总面积减去最后损失的最小面积.

损失的面积是一小块一小块三角形累加起来的.

上个图片仅供参考:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

typedef long long LL;

const int maxn = 100 + 10;

struct Point

{

    LL x, y;

    Point(LL x = 0, LL y = 0) : x(x), y(y) {}

    void read() { scanf("%lld%lld", &x, &y); }

};

Point operator - (const Point& A, const Point& B) {

    return Point(A.x - B.x, A.y - B.y);

}

bool operator < (const Point& A, const Point& B) {

    return A.x < B.x || (A.x == B.x && A.y < B.y);

}

LL Cross(const Point& A, const Point& B) {

    return A.x * B.y - A.y * B.x;

}

vector<Point> p, con;

vector<Point> ConvexHull() {

    sort(p.begin(), p.end());

    int n = p.size();

    vector<Point> ch(n);

    int m = 0;

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

        while(m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) < 0) m--;

        ch[m++] = p[i];

    }

    int k = m;

    for(int i = n - 2; i >= 0; i--) {

        while(m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) < 0) m--;

        ch[m++] = p[i];

    }

    if(n > 1) m--;

    ch.resize(m);

    return ch;

}

int n, k;

LL d[maxn][maxn];

bool vis[maxn];

int main()

{

    //freopen("in.txt", "r", stdin);

    int _; scanf("%d", &_);

    for(int __ = 1; __ <= _; __++) {

        scanf("%d%d", &n, &k);

        p.resize(n);

        for(int i = 0; i < n; i++) p[i].read();

        con = ConvexHull();

        int sz = con.size();

        if(sz <= 2 || k <= 2) { printf("0\n"); continue; }

        LL totarea = 0;

        for(int i = 2; i < sz; i++) totarea += Cross(con[i-1]-con[0], con[i] - con[0]);

        if(k >= sz) {

            printf("%lld\n", totarea);

            continue;

        }

        LL ans = 0x3f3f3f3f3f3f3f3f;

        memset(vis, false, sizeof(vis));

        int times = min(10 * n / k, sz);

        while(times--) {

            int s = rand() % sz;

            while(vis[s]) s = rand() % sz;

            vis[s] = true;

            memset(d, 0x3f, sizeof(d));

            d[0][0] = 0;

            for(int i = 1; i <= sz; i++) {

                int p0 = (s + i) % sz;

                LL cut = 0;

                for(int j = i - 1; j >= 0; j--) {

                    int p2 = (s + j) % sz;

                    int p1 = (p2 + i) % sz;

                    cut += Cross(con[p1] - con[p0], con[p2] - con[p0]);

                    for(int l = k; l > 0; l--)

                        d[i][l] = min(d[i][l], d[j][l-1] + cut);

                }

            }

            ans = min(ans, d[sz][k]);

        }

        printf("Case #%d: %lld\n", __, totarea - ans);

    }

    return 0;

}

巴特西

HDU 5473 There was a kingdom 凸包 DP

题意:

分析:

最新文章

热门文章