凸多边形的划分

题目 凸多边形的划分

给定一个具有 N 个顶点的凸多边形，将顶点从 1 至 N 标号，每个顶点的权值都是一个正整数。

将这个凸多边形划分成 N−2 个互不相交的三角形，对于每个三角形，其三个顶点的权值相乘都可得到一个权值乘积，试求所有三角形的顶点权值乘积之和至少为多少。

即：求所有三角形的顶点权值乘积之和的最小值

输入格式 第一行包含整数 N，表示顶点数量。

第二行包含 N 个整数，依次为顶点 1 至顶点 N 的权值。

输出格式 输出仅一行，为所有三角形的顶点权值乘积之和的最小值。

数据范围 N≤50,数据保证所有顶点的权值都小于109

输入样例：

5

121 122 123 245 231

输出样例：

12214884

思路分析

给定 n 个点的 凸多边形 中每个 顶点 的 权值 \(w_i\) 我们可以把该 凸多边形 划分成 n - 2 个 三角形（三角形不能相交，这样就能保证是 n−2n−2 了）

每次划分三角形的 费用 为 三个顶点权值 的 乘积

求一个划分 方案，s.t.方案的 费用总和 最小

这是一个经典的 图形学 问题 —— 三角剖分

因为我们现实中常见的一些 多边形图形 存储到计算机中，需要转存为一个个 像素点

那么如何存储一个 多边形 最简单的方案就是把它转化为 多个三角形 进行存储

也就是 三角剖分 问题，不只是 凸多边形，还能解决 凹多边形， 有孔多边形 等问题

对应有 O(n3) 的暴力算法，O(n2)的 earclipping 算法，O(nlogn) 的 Delaunay算法

还有很复杂的线性算法

回归本题，本题是一个给定的 凸多边形 求 三角剖分 的最小费用方案

• 第一行是以点为出发视角讨论有哪些三角形，这和题目是完全一致的。
• 第二行是以边为出发视角讨论有哪些三角形，并且，只绘制了相邻点构成的边。 那不相邻的点就无法构成边吗？再以这条构成边出发，是不是还可以继续绘制其它三角形呢？ 是的，比如1点和3点也可以构成边，就是先把1,3用线连起来，但这个肯定会与以其它相邻点构成的三角形重复，只讨论相邻的就可以覆盖掉全部的三角形。

很显然一个 凸多边形的剖分方案 并不唯一：

在 选定 多边形中 两个点 后，找出 三角形 的 第三个点 的方案有 n−2个

然后还要分别 划分 他的 左右两块区域

因此 可以转化为求区间[1,n]之间所有可构成三角形的公式和最小值

闫氏DP分析法

状态表示—集合 f[l][r]:多边形的所有边【即：(l,l+1),(1+1,l+2),…,(r−1,r),(l,r)】划分成三角形的所有方案

状态表示—属性 f[l][r]:方案的最小费用

状态计算

其三个顶点的权值相乘都可得到一个权值乘积，试求所有三角形的顶点权值乘积之和至少为多少。

所以代价是\(w_l×w_k×w_j\)则状态转移方程：

f[l][r]=min(f[l][k]+f[k][r]+w[l]×w[k]×w[r])(l<k<r)

k的取值范围也很好理解：三个点才能形成三角形，如果l=k或者k=r都将无法形成三角形。

区间DP 在状态计算的时候一定要 认真 划分好 边界 和 转移，对于不同题目是不一样的

然后本题非常的嚣张，直接用样例的 5 的点告诉我们答案会爆 int 和 long long

并且没有 取模 要求，那就只能上 高精度 了,要是懒的话，那用一下__int128,这个是yyds

本题因为是三个\(10^9\)的数字相乘为最大值范围:

int:2147483648,即\(2^{31}≈2×10^{10}\)

long long ：9223372036854775807 ,即\(2^{63}≈9×10^{19}\)

三个 int连乘就是 \(2∗10^{10}×2×10^{10}×2×10^{10}=8×10^{30}\)

long long 也是装不下，只能使用高精度(__int128也可以)

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 210;

const int M = 35;

const int INF = 0x3f3f3f3f;

int n;

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

LL w[N];

// 判断a>b

bool cmp(LL a[], LL b[]) {

    for (int i = M - 1; i >= 0; i--) { // 直接从高位进行比较,如果某一位a[i]>b[i]，则说明a比b这个数大

        if (a[i] > b[i]) return true;

        if (a[i] < b[i]) return false;

    }

    return false;

}

// 直接从0位(个位)加，一直加到最高位M-1位

void add(LL a[], LL b[]) {

    LL c[M] = {0}, t = 0;

    for (int i = 0; i < M; i++) {

        t += a[i] + b[i];

        c[i] = t % 10;

        t /= 10;

    }

    memcpy(a, c, sizeof c);

}

// 从0位(个位)开始乘，一直乘到最高位M-1位

void mul(LL a[], LL b) {

    LL c[M] = {0}, t = 0;

    for (int i = 0; i < M; i++) {

        t += a[i] * b;

        c[i] = t % 10;

        t /= 10;

    }

    memcpy(a, c, sizeof c);

}

// 打印高精度结果数组

void print(LL a[]) {

    int k = M - 1;

    while (k && !a[k]) k--; // 输出之前要将所有的前导0都去掉

    for (int i = k; i >= 0; i--) printf("%lld", a[i]);

    puts("");

}

int main() {

    scanf("%d", &n);

    for (int i = 1; i <= n; i++) scanf("%d", &w[i]);

    for (int len = 3; len <= n; len++) {

        for (int l = 1; l + len - 1 <= n; l++) {

            int r = l + len - 1;

            f[l][r][M - 1] = 1; // 因为高精度数组是高位在右，低位在左，这里设置的是最高位为1，目的是什么呢？

            for (int k = l + 1; k < r; k++) { // 枚举中间点

                LL t[M] = {0};                // 临时高精度数组

                t[0] = 1;                     // 乘法的世界本原

                mul(t, w[l]);                 // 高精度乘法

                mul(t, w[k]);                 // 高精度乘法

                mul(t, w[r]);                 // 高精度乘法

                add(t, f[l][k]);              // 高精度加法

                add(t, f[k][r]);              // 高精度加法

                // 得到新的最大值，更新

                if (cmp(f[l][r], t)) memcpy(f[l][r], t, sizeof t);

            }

        }

    }

    // 输出

    print(f[1][n]);

    return 0;

}

__int128是什么？

在关于NOI系列活动中编程语言使用限制的补充说明中表明:

允许使用以下划线开头的库函数或宏，但具有明确禁止操作的库函数和宏除外。

所以能在比赛中进行使用。

由于 __int128 仅仅是 (GCC) 编译器内的东西，不在 (C++98/03/11/14/17/20) 标准内， 且仅 (GCC4.6) 以上64位版本支持，很多配套都没有，只有四则运算功能。

目前NOI的GCC版本是9.0,放心使用~

优点

C++内测的一种数据类型,__int128的最大值是： ±85070591730234615865843651857942052864,约为\(10^{38}\)。 足够解决大部分高精度，大数据问题。

缺点

• 手写输入输出

#include <bits/stdc++.h>

using namespace std;

const int N = 55;

typedef __int128 LL;

const LL INF = 1e38;

LL read() {

    LL x = 0, f = 1;

    char ch = getchar();

    while (ch < '0' || ch > '9') {

        if (ch == '-') f = -1;

        ch = getchar();

    }

    while (ch >= '0' && ch <= '9') {

        x = x * 10 + ch - '0';

        ch = getchar();

    }

    return x * f;

}

void write(LL x) {

    if (x < 0) putchar('-'), x = -x;

    if (x > 9) write(x / 10);

    putchar(x % 10 + '0');

}

LL f[N][N];

LL w[N];

int n;

int main() {

    scanf("%d", &n);

    for (int i = 1; i <= n; i++) w[i] = read();

    // 初始化

    for (int i = 1; i <= n; i++)

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

            // 两个点之间最小差距是2，比如[1,3]这里面就有三角形，需要求解，如果小于2，比如[1,2]

            // 无法构成三角形，就不需要求解，无法构成的情况贡献值是0，也是递推的起点，否则，全都是INF

            // 就无法推起来了

            j - i < 2 ? f[i][j] = 0 : f[i][j] = INF;

    for (int len = 3; len <= n; len++) { // 区间范围最少是3个，否则无法构建三角形

        for (int l = 1; l + len - 1 <= n; l++) {

            int r = l + len - 1;

            for (int k = l + 1; k < r; k++) // l<k<r才能构建三角形

                f[l][r] = min(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);

        }

    }

    // 输出

    write(f[1][n]);

    return 0;

}

代码实现

同类题型

视频讲解

---

⬅️ 飞行员兄弟 🏠 00-刷题理模型 ➡️ 加分二叉树