5
0 0
2 0
3 1
2 2
0 2
1 2 3 4 5

30

dp[i][j] = min_{k = i+1}^{j-1} ( dp[i][k] + dp[k][j] + cost(i, k, j) )

dp[i][j] = 0,                                  如果 j == i+1（只有一条边，不需要对角线）
dp[i][j] = min_{k = i+1}^{j-1} ( dp[i][k] + dp[k][j] + (w[i] + w[k] + w[j]) ), 如果 j > i+1

多边形的最优三角形剖分（最小内角和） 题目描述 已知一个凸多边形有 n 个顶点，按顺时针顺序给出每个顶点的坐标。我们可以用 n-3 条不相交的对角线将这个多边形剖分成 n-2 个三角形。定义每个三角形的“内角和代价”为该三角形三个内角的和（以弧度或角度为单位，但结果需一致）。请设计一个算法，找出一种三角形剖分方案，使得所有 n-2 个三角形的内角和代价之和最小。由于多边形是凸的，任意由多边形顶点构成的三角形其内角和均为常数（例如，若用角度制，恒为 180°），因此每个三角形的代价是固定的，与选择哪三个顶点无关。那么，问题转化为：找出使三角形总数最小（即 n-2 个）的剖分，但其总代价却固定？等等，这里需要重新审视。 问题澄清与修正 实际上，三角形内角和是恒定的（例如 π 弧度）。因此，不论如何剖分，n-2 个三角形的内角和总和总是固定的： (n-2) * π 。所以，如果代价就是内角和，那么所有剖分方案的代价都相同，问题就失去了优化意义。 但原问题通常的变体是：每个三角形的“代价”是其三个顶点上某种权重的函数（例如顶点权重之和、三边长度之和、三角形面积等）。为了使题目有意义，我们重新定义代价：给定凸多边形顶点 P[0], P[1], ..., P[n-1] ，用对角线剖分后，每个三角形由顶点 (i, j, k) 组成，其代价定义为 weight(i) + weight(j) + weight(k) ，其中 weight(i) 是顶点 i 的给定权重值（非负）。目标是找到一种三角剖分，使得所有三角形的代价总和最小。 输入格式 第一行：整数 n (n ≥ 3)，表示凸多边形顶点数。 接下来 n 行：每行两个整数 x, y 表示顶点坐标（凸性已保证，按顺时针顺序给出）。 最后 n 行（或同一行）：n 个整数 w[0], w[1], ..., w[n-1] ，表示每个顶点的权重。 输出格式 一个整数，表示最小的总代价。 示例 输入： 输出： 解题过程 第一步：理解问题与子结构 我们有一个凸多边形，顶点编号 0 到 n-1 ，顺时针排列。三角剖分是将多边形划分为若干个三角形，使得这些三角形的并集等于原多边形，且任意两个三角形无重叠内部区域。 由于是凸多边形，任何由不相交对角线组成的三角剖分都等价于选择一组对角线，使得这些对角线在多边形内部构成一个树状结构（实际是一棵“三角剖分树”）。但动态规划常用的一种视角是：考虑多边形的一条边 (i, j) （其中 j > i ，或者对环形取模），然后选择一个顶点 k （ i < k < j ），用对角线 (i, k) 和 (k, j) 将多边形 [i, j] 区域分割为一个三角形 (i, k, j) 和两个子多边形 [i, k] 和 [k, j] 。 但注意：如果我们固定多边形的一条边 (i, j) ，并希望剖分这个边所对应的多边形区域（即从顶点 i 顺时针到顶点 j 的部分），那么我们需要保证这个区域是一个连续的多边形链。实际上，对于凸多边形，如果我们考虑顶点区间 [i, j] （按顺时针顺序），那么边 (i, j) 要么是多边形的外边，要么是一条对角线。如果我们定义 dp[i][j] 表示从顶点 i 到顶点 j 的顺时针链所构成的多边形的最小剖分代价（其中 i < j ，且链包含顶点 i, i+1, ..., j），那么如何剖分呢？ 我们可以选择中间顶点 k （ i < k < j ），三角形 (i, k, j) 一定是剖分中的一个三角形（因为它是覆盖边 (i, j) 的一个三角形）。这个三角形将原链多边形分割为两个子链多边形： [i, k] 和 [k, j] 。因此，递推式为： 其中 cost(i, k, j) = w[i] + w[k] + w[j] 。 边界条件：当链多边形只有两个顶点时（即 j == i+1 ），它只是一条边，无法构成三角形，因此 dp[i][i+1] = 0 。 最终答案是什么？我们考虑整个多边形，它对应顶点链 [0, n-1] ，因此答案为 dp[0][n-1] 。 但是，这里有一个陷阱：我们的链 [i, j] 包含顶点 i, i+1, ..., j，但边 (i, j) 可能不是原多边形的外边，而是一条对角线。然而，在凸多边形中，只要顶点按顺序，边 (i, j) 总是合法的（要么是外边，要么是对角线），且三角形 (i, k, j) 内部一定在多边形内部。因此递推成立。 第二步：确定 DP 状态与递推 状态： dp[i][j] 表示从顶点 i 顺时针到顶点 j 的链所构成的多边形（包含边 (i, j) ）的最小三角剖分代价（即三角形顶点权重和的总和）。其中 0 ≤ i < j ≤ n-1 。 递推： 解释：选择中间点 k，将链多边形分割为子链 [i, k] 和 [k, j] ，并新增一个三角形 (i, k, j) ，其代价为三个顶点权重之和。 因为凸多边形是环形的，我们需要考虑链的起点和终点。但我们的定义已经通过 i 和 j 确定了链的方向（顺时针），所以无需担心环形。 但注意：整个多边形是 [0, n-1] ，但还有一条边 (n-1, 0) 也是外边。在我们的链表示中，边 (n-1, 0) 没有被包含。然而，整个多边形的三角剖分一定会包含三角形 (0, k, n-1) 吗？不一定，因为如果选择另一个顶点作为中间点，比如 m ，那么三角形 (0, m, n-1) 可能不出现。但我们的链 [0, n-1] 对应的是从 0 顺时针到 n-1 的部分，它包含了顶点 0,1,...,n-1，但边 (n-1, 0) 不在这个链中。因此，整个多边形被表示为链 [0, n-1] ，其剖分确实会以某个 k 为中间点形成三角形 (0, k, n-1) ，因为这是覆盖边 (0, n-1) 的唯一方式（在凸多边形中，边 (0, n-1) 是多边形的一条外边，必须被一个三角形覆盖）。所以递推正确。 第三步：处理环形问题 然而，凸多边形是环形的，链 [0, n-1] 只是多边形的一部分吗？实际上，多边形顶点是循环的。我们的链 [0, n-1] 包含了所有顶点，所以它就是整个多边形。但边 (n-1, 0) 是外边，它没有被包含在链的边集合中。我们的链多边形定义中，边 (i, j) 是链的一条边，而其他边是 (i, i+1), (i+1, i+2), ..., (j-1, j) 。对于链 [0, n-1] ，这些边正好是多边形的所有外边，除了 (n-1, 0) 。但 (n-1, 0) 作为外边，在三角剖分中必须被某个三角形覆盖。这个三角形会以 (n-1, 0) 为一边，第三个顶点是某个 m （ 0 < m < n-1 ）。这个三角形就是 (0, m, n-1) ，它正好出现在我们的递推中（当 k=m ）。所以链 [0, n-1] 的剖分确实对应了整个多边形的剖分。 因此，我们不需要特殊处理环形，因为链 [0, n-1] 已经覆盖了整个多边形（只是少了一条外边，但该外边会被三角形覆盖）。 第四步：计算顺序 由于 dp[i][j] 依赖于 dp[i][k] 和 dp[k][j] ，其中 i < k < j ，所以我们可以按区间长度 len 从小到大计算。 len = j - i ，从 len = 1 开始（即 j = i+1 ），然后逐步增大到 len = n-1 （即 j = i + n-1 ，但注意 j ≤ n-1 ，所以最大 len = n-1 对应 i=0, j=n-1 ）。 因此： 初始化 dp[i][i+1] = 0 。 对于 len 从 2 到 n-1（因为 len=1 已处理）： 对于每个 i 从 0 到 n-1-len： 令 j = i + len 。 枚举 k 从 i+1 到 j-1 ，计算 dp[i][j] = min(dp[i][k] + dp[k][j] + w[i] + w[k] + w[j]) 。 注意：当 len=2 时，多边形有三个顶点 (i, i+1, i+2) ，此时只能选择 k = i+1 ，形成一个三角形，代价为 w[i]+w[i+1]+w[i+2] ，与递推一致。 第五步：示例演算 考虑简单例子 n=4，顶点权重 w=[ 1,2,3,4 ]。 多边形为四边形 (0,1,2,3)。我们计算 dp[0][3] 。 首先初始化： dp[0][1]=0 , dp[1][2]=0 , dp[2][3]=0 , dp[0][2] 和 dp[1][3] 需要计算。 计算 dp[0][2] （len=2, i=0, j=2）： k 只能为 1： dp[0][2] = dp[0][1] + dp[1][2] + w[0]+w[1]+w[2] = 0 + 0 + 1+2+3 = 6 。 计算 dp[1][3] （len=2, i=1, j=3）： k 只能为 2： dp[1][3] = dp[1][2] + dp[2][3] + w[1]+w[2]+w[3] = 0+0+2+3+4=9 。 现在计算 dp[0][3] （len=3, i=0, j=3）： 枚举 k=1,2。 k=1: dp[0][1] + dp[1][3] + w[0]+w[1]+w[3] = 0 + 9 + 1+2+4 = 16 k=2: dp[0][2] + dp[2][3] + w[0]+w[2]+w[3] = 6 + 0 + 1+3+4 = 14 取最小值 14。 所以最小总代价为 14。 验证：四边形有两种三角剖分：对角线 (0,2) 或 (1,3)。 对角线 (0,2)：三角形 (0,1,2) 代价 1+2+3=6，三角形 (0,2,3) 代价 1+3+4=8，总和 14。 对角线 (1,3)：三角形 (0,1,3) 代价 1+2+4=7，三角形 (1,2,3) 代价 2+3+4=9，总和 16。 所以最小为 14，匹配。 第六步：复杂度分析 状态数 O(n²)，每个状态需要枚举 O(n) 个中间点 k，总时间复杂度 O(n³)。空间复杂度 O(n²)。对于 n ≤ 200 是可行的。 第七步：最终答案 答案就是 dp[0][n-1] 。 注意：如果 n=3，那么多边形本身就是一个三角形，不需要对角线，但代价就是这个三角形的权重和。我们的递推中， dp[0][2] 对应 len=2，计算得到 w[0]+w[1]+w[2] ，正确。 第八步：扩展思考 本题的代价函数是顶点权重之和，这是一个常见的简化。实际问题中代价可能是三角形周长、面积或其他自定义函数。只要代价函数可以在 O(1) 时间内计算，且满足最优子结构（即整体最优包含子问题最优），DP 方法依然适用。如果多边形非凸，三角剖分仍然存在，但需要保证对角线在多边形内部，这时判断合法性会复杂，可能需要几何检查。对于凸多边形，任意 i, k, j 构成的三角形都在多边形内部，因此简化了许多。 通过这个 DP 框架，我们可以在 O(n³) 时间内求解凸多边形的最优三角剖分问题（基于顶点权重和的最小化）。