\(\text{Solution}\)

发现每个时刻的状态一定是所有点在一个最外围三角形的内部

设 \(f_{i,j,k,p}\) 表示排列填到第 \(p\) 位，此时图形最外围的三角形是以编号为 \(i,j,k\) 的三角形的方案数

那么考虑这个三角形是怎么来的，于是又两个转移

1.前 \(1~p-1\) 位已经填出了 \(i,j,k\) 这个三角形，那么这一位就可以填这个三角形内部还没填的点

2.到第 \(p\) 位才填出这个三角形，那么这个三角形一定是从一个小三角形转移过来，枚举内部一个点，令它与 \(i,j,k\) 中任意两点组成小三角形转移即可

判断一个点是否在某个三角形内部可以用面积，面积用叉乘算即可

显然这个 \(dp\) 是 \(O(n^5)\) 的

考虑优化，强制枚举的 \(i<j<k\)

这个就优秀很多了，\(JZOJ\) 上可以过，\(LG\) 上要开 \(O\)

\(\text{Code}\)

#include <cstdio>

#include <cmath>

#include <iostream>

#define LL long long

#define re register

using namespace std;

const int N = 45;

const LL P = 1e9 + 7;

int n, h[N][N][N];

LL f[N][N][N][N];

struct Point{

	double x, y;

	inline Point(double xx = 0, double yy = 0){x = xx, y = yy;}

	inline Point operator - (const Point &B){return Point(x - B.x, y - B.y);}

}a[N];

inline double Cross(const Point &A, const Point &B){return fabs(A.x * B.y - A.y * B.x);}

inline double Area(int i, int j, int k){return Cross(a[i] - a[j], a[k] - a[j]);}

inline int isIn(int i, int j, int k, int l)

{

	return fabs(Area(i, j, k) - Area(i, j, l) - Area(j, k, l) - Area(i, k, l)) <= 1e-6;

}

inline void Add(LL &x, LL y){x = (x + y) % P;}

inline void trans(int p, int i, int j, int k, int x, int y, int z)

{

	if (z < x) swap(x, z);

	if (z < y) swap(y, z);

	Add(f[i][j][k][p], f[x][y][z][p - 1]);

}

int main()

{

	scanf("%d", &n);

	for(re int i = 1, x, y; i <= n; i++) scanf("%d%d", &x, &y), a[i] = Point(x, y);

	for(re int i = 1; i <= n - 2; i++)

		for(re int j = i + 1; j <= n - 1; j++)

			for(re int k = j + 1; k <= n; k++)

				for(re int l = 1; l <= n; l++)

				if (l ^ i && l ^ j && l ^ k) h[i][j][k] += isIn(i, j, k, l);

	for(re int i = 1; i <= n - 2; i++)

		for(re int j = i + 1; j <= n - 1; j++)

			for(re int k = j + 1; k <= n; k++) f[i][j][k][3] = 6;

	for(re int p = 4; p <= n; p++)

	for(re int i = 1; i <= n - 2; i++)

		for(re int j = i + 1; j <= n - 1; j++)

			for(re int k = j + 1; k <= n; k++)

			{

				if (h[i][j][k] - p + 4 > 0) Add(f[i][j][k][p], f[i][j][k][p - 1] * (h[i][j][k] - p + 4) % P);

				for(re int l = 1, x, y, z; l <= n; l++)

				if (l ^ i && l ^ j && l ^ k && isIn(i, j, k, l))

					trans(p, i, j, k, i, j, l), trans(p, i, j, k, i, k, l), trans(p, i, j, k, j, k, l);

			}

	LL ans = 0;

	for(re int i = 1; i <= n - 2; i++)

		for(re int j = i + 1; j <= n - 1; j++)

			for(re int k = j + 1; k <= n; k++)

				ans = (ans + f[i][j][k][n]) % P;

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

}

巴特西

【USACO 2021 US Open, Gold】Permutation

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章