「一本通 5.1 例 3」凸多边形的划分

形式化题目

给定凸 $N$ 边形，顶点按边界顺序编号 $1..N$ ，顶点 $i$ 的权值 $w_i$ 为正整数。把它划分成 $N-2$ 个互不相交的三角形（即标准三角剖分：每个三角形以三个顶点为顶、边是原多边形的边或对角线，覆盖整个多边形且内部不交），每个三角形取三顶点权值之积 $w_a w_b w_c$ ，求全部三角形乘积之和的最小值。

样例： $N = 5$ ，权值依次为 121 122 123 245 231，输出 12214884。

正解

思路

一句话本质：利用"边界边必属于唯一三角形"，枚举与边界边组成三角形的顶点 $k$ ，把区间劈成两个独立子多边形，用区间 DP 求最小乘积和。

朴素做法与瓶颈。 最直接的想法是枚举所有三角剖分再逐个求和：剖分数是 Catalan 数 $C_{N-2} \approx 1.3 \times 10^{26}$ （ $N=50$ ），完全不可行。慢的根源不是求和，而是重叠子问题：任意一段"边界上连续顶点构成的子多边形"，它的最优剖分只与这段顶点本身有关，与外层怎么拼接无关；枚举整剖分时，同一个子多边形的最优值被重复计算了指数多次。

关键观察：劈分结构。 记 $[i..j]$ 为边界上连续的一段顶点构成的凸多边形：

当 $j > i + 1$ 时， $(i, j)$ 是这段子多边形的边界边，而三角剖分中每条边界边恰属于一个三角形，所以它必属于某个三角形 $(i, k, j)$ ， $i < k < j$ 。
三角形 $(i, k, j)$ 的两条弦 $(i, k)$ 、 $(k, j)$ 把 $[i..j]$ 劈成两段更小的、顶点仍连续的凸多边形 $[i..k]$ 与 $[k..j]$ （ $k$ 与端点相邻时一侧退化成一条边）。两段内部不交、三角形互不共享，且权值全为正，所以两段各自取最优即整体最优。

于是"最后一个决策"就是选哪个 $k$ ，得到区间 DP（ $f[i][j]$ = 子多边形 $[i..j]$ 的最小乘积和）：

f[i][j] = \min_{i < k < j} \big( f[i][k] + f[k][j] + w_i \cdot w_k \cdot w_j \big), \qquad f[i][i] = f[i][i+1] = 0

答案是 $f[1][N]$ （代码 0-based 写作 f[0][n-1]）。两段的 $j - i$ 一定比原区间小，所以按 gap 从小到大递推即可保证用到的子状态都已算出。

样例的 DP 表。 下表是样例的全部 $f[i][j]$ （行 = 左端点 $i$ ，列 = 右端点 $j$ ，- 表示 $i > j$ 的无效格，对角线与相邻格是边界值 $0$ ；单元格 = 该段子多边形的最小乘积和）：

$i \backslash j$	1	2	3	4	5
1	0	0	1815726	5462061	12214884
2	-	0	0	3676470	10427571
3	-	-	0	0	6961185
4	-	-	-	0	0
5	-	-	-	-	0

观察重点：gap $= 2$ 的格子直接等于三顶点之积（如 $f[1][3] = 121 \times 122 \times 123 = 1815726$ ）；越靠右上 gap 越大，每格只依赖 gap 更小的格子。右上角 $f[1][5]$ 的三个候选：

k = 2:\ 0 + 10427571 + 121 \cdot 122 \cdot 231 = 13837593

k = 3:\ 1815726 + 6961185 + 121 \cdot 123 \cdot 231 = 12214884 \quad \text{（最优）}

k = 4:\ 5462061 + 0 + 121 \cdot 245 \cdot 231 = 12310056

即先用三角形 $(1, 3, 5)$ 把五边形劈成 $[1..3]$ 与 $[3..5]$ 两段，两段各自取最优（都恰好是三角形），得到 $12214884$ ，与样例输出一致。

正确性。 对 gap $= j - i$ 归纳：gap $\leqslant 1$ 时顶点不足三个、无三角形可划， $f = 0$ 显然。一般情形下，由观察 1 任一剖分都对应唯一的一个 $k$ ，由观察 2 该剖分的代价恰等于"两段剖分代价 $+$ $w_i w_k w_j$ "，不同 $k$ 对应互不相同的剖分集合；枚举全部 $k$ 且两段取各自最优，覆盖所有方案且不重不漏，故 min 即全局最优。

边界与溢出。 $N = 3$ 时外层只算 gap $= 2$ 一个格子，输出唯一三角形的乘积。权值 $< 10^9$ 时单个乘积达 $10^{27}$ 、总和最多 $48$ 项约 $4.8 \times 10^{28}$ ，超过 64 位整数范围——C++ 需要高精度，而 Python 的 int 是任意精度的，直接写乘加即可。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 19:01
# update_at: 2026-09-30 19:01

import sys


def min_product_sum(weight: list[int]) -> int:
    """凸多边形划分：f[i][j] = 顶点 i..j 这段子多边形的最小三角形乘积和。"""
    n = len(weight)
    f = [[0] * n for _ in range(n)]  # 相邻两点只是一条边，权值和天然为 0
    for gap in range(2, n):  # gap = j - i，至少 3 个顶点才需要划分
        for i in range(n - gap):
            j = i + gap
            # 选中间顶点 k，三角形 (i, k, j) 把子多边形劈成 [i..k]、[k..j] 两段
            f[i][j] = min(
                f[i][k] + f[k][j] + weight[i] * weight[k] * weight[j]
                for k in range(i + 1, j)
            )
    return f[0][n - 1]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 顶点数
    weight = [next(data) for _ in range(n)]  # 顶点 1..N 的权值
    print(min_product_sum(weight))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 09:12
 * update_at: 2026-10-05 09:12
 */
// 凸多边形三角剖分的最小乘积和：区间 DP + 高精度。
// f[i][j] = 子多边形 [i..j] 的最小乘积和，枚举与边界边 (i,j) 组成
// 三角形的顶点 k，劈成 [i..k] 与 [k..j] 两段：
//   f[i][j] = min{ f[i][k] + f[k][j] + w_i * w_k * w_j }
// 权值 < 1e9 时单个乘积可达 ~1e27，总和 ~1e29，超出 64 位整数，必须高精度。
#include <cstdio>

typedef long long ll;

const int MAXN = 55;         // 顶点数上限
const ll BASE = 1000000000;  // 高精度压 9 位十进制
const int MAXD = 6;          // 每个大数最多 6 段，可存 ~1e54，足够

// 压位高精度整数：低位在前，每段存 9 位十进制
struct Big {
    int len;      // 有效段数，len = 0 表示数值 0
    ll d[MAXD];   // d[i] 是第 i 段，0 <= d[i] < BASE
};

ll n;                        // 顶点数
ll w[MAXN];                  // w[i] 为顶点 i 的权值
Big f[MAXN][MAXN];           // f[i][j]：子多边形 [i..j] 的最小乘积和（高精度）

// 大数清零
void big_zero(Big &a) {
    a.len = 0;
}

// 大数加法：c = a + b
Big big_add(Big a, Big b) {
    Big c;
    int len = a.len > b.len ? a.len : b.len;
    ll carry = 0;
    for (int i = 0; i < len; i++) {
        ll cur = carry;
        if (i < a.len) cur += a.d[i];
        if (i < b.len) cur += b.d[i];
        c.d[i] = cur % BASE;
        carry = cur / BASE;
    }
    c.len = len;
    while (carry > 0) {          // 进位可能多出一段
        c.d[c.len] = carry % BASE;
        carry /= BASE;
        c.len++;
    }
    return c;
}

// 大数乘小整数：c = a * b（b < 1e9，保证中间结果不溢出）
Big big_mul_ll(Big a, ll b) {
    Big c;
    if (b == 0 || a.len == 0) {  // 乘 0 直接得 0
        c.len = 0;
        return c;
    }
    ll carry = 0;
    for (int i = 0; i < a.len; i++) {
        ll cur = a.d[i] * b + carry;
        c.d[i] = cur % BASE;
        carry = cur / BASE;
    }
    c.len = a.len;
    while (carry > 0) {
        c.d[c.len] = carry % BASE;
        carry /= BASE;
        c.len++;
    }
    return c;
}

// 比较大小：a < b 返回 -1，相等返回 0，a > b 返回 1
int big_cmp(Big a, Big b) {
    if (a.len != b.len) {        // 段数少（无前导零段）的数一定小
        return a.len < b.len ? -1 : 1;
    }
    for (int i = a.len - 1; i >= 0; i--) {  // 从最高段往低位比
        if (a.d[i] != b.d[i]) return a.d[i] < b.d[i] ? -1 : 1;
    }
    return 0;
}

// 输出大数：最高段不带前导零，其余段补满 9 位
void big_print(Big a) {
    if (a.len == 0) {            // len = 0 表示 0
        printf("0\n");
        return;
    }
    printf("%lld", a.d[a.len - 1]);
    for (int i = a.len - 2; i >= 0; i--) {
        printf("%09lld", a.d[i]);
    }
    printf("\n");
}

int main() {
    scanf("%lld", &n);
    for (ll i = 1; i <= n; i++) scanf("%lld", &w[i]);

    // 边界：不足 3 个顶点没有三角形，f = 0
    for (int i = 1; i <= (int)n; i++) {
        big_zero(f[i][i]);
        if (i < (int)n) big_zero(f[i][i + 1]);
    }

    // len = 区间长度 - 1（即 j - i），从小到大保证子状态已算出
    for (int len = 2; len < (int)n; len++) {
        for (int i = 1; i + len <= (int)n; i++) {
            int j = i + len;
            bool first = true;   // 是否第一次赋值（用于初始化最小值）
            for (int k = i + 1; k < j; k++) {
                // 三顶点乘积：从 w[i] 的大数形式逐步乘 w[k]、w[j]
                Big wi;
                wi.len = 0;
                ll t = w[i];
                while (t > 0) {  // 权值转成大数（压 9 位）
                    wi.d[wi.len] = t % BASE;
                    t /= BASE;
                    wi.len++;
                }
                Big product = big_mul_ll(wi, w[k]);
                product = big_mul_ll(product, w[j]);
                Big cand = big_add(big_add(f[i][k], f[k][j]), product);
                if (first || big_cmp(cand, f[i][j]) < 0) {
                    f[i][j] = cand;
                    first = false;
                }
            }
        }
    }

    big_print(f[1][n]);
    return 0;
}

复杂度

时间复杂度： $O(N^3)$ ，gap、左端点、 $k$ 三重循环； $N = 50$ 时转移次数 $\binom{50}{3} \approx 2 \times 10^4$ ，在 1000 ms 内绰绰有余。
空间复杂度： $O(N^2)$ ， $50 \times 50$ 的 DP 表加 $O(N)$ 的读入。

总结

凸多边形三角剖分的最优子结构：边界边必属于唯一三角形，选劈分顶点 $k$ 后问题拆成两个连续区间的独立子问题，正权值保证两段可以各自取最优。
状态 $f[i][j]$ = 连续顶点子多边形的最小乘积和，边界是 gap $\leqslant 1$ 的 $0$ ，按 gap 递增递推，答案 $f[1][N]$ 。
"枚举整个方案"是 Catalan 级暴力；"枚举最后一个决策 + 记忆化子问题"把它降到 $O(N^3)$ ，这是区间 DP 的通用套路。
权值 $10^9$ 下总和可达 $\sim 10^{28}$ ，这题在 C++ 里要配高精度，Python 大整数天然免掉这一层。

图示解析

下图是样例最优剖分的顶点环（红色为剖分引入的对角线）：

graph LR
    v1["1<br/>121"] --- v2["2<br/>122"]
    v2 --- v3["3<br/>123"]
    v3 --- v4["4<br/>245"]
    v4 --- v5["5<br/>231"]
    v5 --- v1
    v1 --- v3
    v3 --- v5
    linkStyle 5,6 stroke:#d33,stroke-width:2px;

三个三角形 $(1,2,3)$ 、 $(1,3,5)$ 、 $(3,4,5)$ 的乘积分别是 $1815726$ 、 $3437973$ 、 $6961185$ ，和为 $12214884$ 。观察重点：两条红对角线正是 DP 在 $f[1][5]$ 处选中 $k=3$ 产生的三角形 $(1,3,5)$ ，以及它劈出的两段 $[1..3]$ 、 $[3..5]$ 各自的唯一三角形——图与上文 DP 表的右上角逐格对应。