[DP记录]P7529 [USACO21OPEN] Permutation G

模拟赛搬了这个题…… **题意** ： 给定二维平面上 $n$ 个点. 统计有多少个 $1\sim n$ 的排列 $P$ 满足 ： 将前三个点连在一起后，在之后的点中，向在排列中在它前面的点连边，有且只有三个不会和之前的线段相交，随后只保留这三条边。 数据保证三点不共线，答案对 $10^9+7$ 取模。 $n\leq 40$ ，时限$\texttt{1s}$。 ------------ 手玩不难发现，加点过程中，凸包一定是个三角形，而且内部是个三角剖分。 加点可以分为两类 ： - 外加：不一定合法，加点后凸包要是三角形才合法。 - 内加：由于内部是三角剖分，一定合法。 不难发现，我们只需要关注凸包上的三个点，以及内部没有被加的点数。 记 $dp[i][j][k][c]$ 表示三角形 $(i,j,k)$ 内部还有 $c$ 个点没加的方案数，转移时枚举外加的点，将新框住的点加入 $c$ 中。 这需要预处理 $s[i][j][k]$ 表示三角形 $(i,j,k)$ 内部的点数，暴力即可。 复杂度为 $O(n^5)$。 ```cpp ```