动规凸包奇妙相遇夜
|
931 字

动规凸包一相逢，便胜却 oi 无数

CF1146H Satanic Panic

二维平面上有 $n$ 个点，找出来五个点使得形成一个五角星，求方案数。

首先五角星可以转化成 $5$ 个点的凸包，然后就可以用计算几何来求解。

怎么判断是否合法呢？可以用叉积，当然也可以通过极角排序保证合法，我用的是后者。

然后就是统计答案，这里用 DP，$f[i][j][k]$ 表示 $i$ 到 $j$ 有 $k$ 条路径。

对于每条边而言都有 $f[x_i][y_i][1]=1$，即初始化；

再考虑转移，对于点 $j$，$f[j][x_i][k]=f[j][x_i][k]+f[j][y_i][k-1]$；

最后的答案是 $\sum_{i=1}^{n}f[i][i][5]$，即所有从自身出发，经过$5$条边又能回到自身的方案数。

最后是代码，注意 Line 中 x，y 为点的编号。

#include<bits/stdc++.h>
using namespace std;
long long f[333][333][6];
int n, cnt;
struct Point {
    double x, y;
} point[100010];
struct Line {
    int x, y; double sigma;
    void MakeLine (int a, int b) {
        x = a, y = b; sigma = atan2(point[b].y-point[a].y, point[b].x-point[a].x); }
    friend bool operator < (Line a, Line b) {
        return a.sigma < b.sigma; }
} line[100010];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lf%lf", &point[i].x, &point[i].y);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i!=j) line[++cnt].MakeLine(i, j);
    sort(line+1, line+cnt+1);
    for (int i = 1; i <= cnt; i++) {
        f[line[i].x][line[i].y][1] = 1;    
        for (int j = 1; j <= n; j++)
            for (int k = 2; k <= 5; k++)
                f[j][line[i].y][k] += f[j][line[i].x][k-1]; }
    for (int i = 1; i <= n; i++)
        f[0][0][0] += f[i][i][5];
    printf("%lld\n", f[0][0][0]);
    return 0;
}

U243047 convex

给出 $n$ 个点，选择其中若干个点，使得这些点的凸包上点的个数尽量多，保证不存在三个点共线，求最多的点数。

（Official Solution）

考虑优化转移，首先出发点可以枚举，不用放在 $dp$ 数组中。

枚举凸包中的最上面的一个点 $T$，然后用 $dp[i][j]$ 表示最后一个选中的点为 $j$ ，上一个被选中的点为 $i$，凸包上的点数的最大值。

这样的话，相当于我们要从点 $T$ 走一个凸集回到点 $T$。于是 $dp[i][j]$ 可以从 $dp[k][i]$ 转移过来，当且仅当 $k->i$ 的极角小于等于 $i->j$ 的极角。（此处的 “极角” 为 $atan2()$ 函数得到的角度）于是我们考虑调整 dp 顺序为：将所有两个点形成的向量按极角排序，以这个顺序来进行 dp，记录一个 $maxn[i]$ 表示当前走到点 $i$ 的凸包点数最大值，每次 $dp[i][j] = maxn[i] + 1$, 且用 $dp[i][j]$ 更新 $maxn[j]$。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 256;

struct Line  {int x, y; double ang;} line[99999];
struct Point {int x, y;} p[maxn];

int dp[maxn][maxn], mx[maxn];
int n, cnt, ans;

bool cmp(Line a, Line b) {
    return a.ang < b.ang;
}

int main() {	
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d %d", &p[i].x, &p[i].y);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (i != j)
                line[++cnt] = {i, j, atan2(p[i].x - p[j].x, p[i].y - p[j].y)};
    sort(line + 1, line + cnt + 1, cmp);
    
    for (int i = 1; i <= n; i++) {
        memset(mx, 0x8f, sizeof mx);
        memset(dp, 0,    sizeof dp);
        mx[i] = 0;
        for (int j = 1; j <= cnt; j++) {
            int a = line[j].x;
            int b = line[j].y;
            dp[a][b] = mx[a] + 1;
            mx[b] = max(mx[b], dp[a][b]);
        }
        ans = max(ans, mx[i]);
    }
    printf("%d\n", ans);
    return 0;
}

General solution

极角排序，考虑转移。

上一篇
下一篇