|
|
## [$AcWing$ $1069$. 凸多边形的划分 ](https://www.acwing.com/problem/content/1071/)
|
|
|
|
|
|
### 一、题目描述
|
|
|
给定一个具有 $N$ 个顶点的凸多边形，将顶点从 $1$ 至 $N$ 标号，每个顶点的权值都是一个正整数。
|
|
|
|
|
|
将这个凸多边形划分成 $N−2$ 个互不相交的三角形，对于每个三角形，其三个顶点的权值相乘都可得到一个权值乘积，**试求所有三角形的顶点权值乘积之和至少为多少**。
|
|
|
|
|
|
> <font color='red' size=4><b>即：求所有三角形的顶点权值乘积之和的最小值</b></font>
|
|
|
|
|
|
**输入格式**
|
|
|
第一行包含整数 $N$，表示顶点数量。
|
|
|
|
|
|
第二行包含 $N$ 个整数，依次为顶点 $1$ 至顶点 $N$ 的权值。
|
|
|
|
|
|
**输出格式**
|
|
|
输出仅一行，为所有三角形的顶点权值乘积之和的最小值。
|
|
|
|
|
|
**数据范围**
|
|
|
$N≤50$,数据保证所有顶点的权值都小于$10^9$
|
|
|
|
|
|
**输入样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
5
|
|
|
121 122 123 245 231
|
|
|
```
|
|
|
|
|
|
**输出样例**：
|
|
|
```cpp {.line-numbers}
|
|
|
12214884
|
|
|
```
|
|
|
|
|
|
### 二、算法思路
|
|
|
这是一个经典的 **图形学** 问题 — **三角剖分**
|
|
|
|
|
|
因为我们现实中常见的一些 **多边形图形** 存储到计算机中，需要转存为一个个 **像素点**
|
|
|
|
|
|
那么如何存储一个 **多边形** 最简单的方案就是把它转化为 **多个三角形** 进行存储
|
|
|
|
|
|
也就是 **三角剖分** 问题，不只是 **凸多边形**，还能解决 **凹多边形**， **有孔多边形** 等问题
|
|
|
|
|
|
回归本题，本题是一个给定的 **凸多边形** 求 **三角剖分** 的 <font color='blue' size=4><b>最小费用方案</b></font>
|
|
|
|
|
|
|
|
|
#### 题意理解
|
|
|
|
|
|
|
|
|
|
|
|
看完题目描述后，我是一脸懵逼，不知道这是个啥意思。冷静下来看了下其它同学的题解，发现是以区间$DP$思路解决此问题，而区间是指任意两点$[l,r],(l<r)$确定下来的区间,然后再分析。
|
|
|
|
|
|
可是题目中说的是划分为$n-2$个三角形，并且，三角形不相交啊！看他们的题解没有三角形不相交的，这是为什么呢？
|
|
|
|
|
|
自己研究了一下，绘制了上面的图：
|
|
|
|
|
|
- 第一行是以点为出发视角讨论有哪些三角形，这和题目是完全一致的。
|
|
|
- 第二行是以边为出发视角讨论有哪些三角形，并且，只绘制了相邻点构成的边。
|
|
|
那不相邻的点就无法构成边吗？再以这条构成边出发，是不是还可以继续绘制其它三角形呢？
|
|
|
是的，比如$1$点和$3$点也可以构成边，就是先把$1,3$用线连起来，但这个肯定会与以其它相邻点构成的三角形重复，只讨论相邻的就可以覆盖掉全部的三角形。
|
|
|
|
|
|
<font color='red' size=4><b>结论：依题意，可以转化为求区间$[1,n]$之间所有可构成三角形的公式和最小值</b></font>
|
|
|
|
|
|
很显然一个 **凸多边形的剖分方案** 并不唯一：
|
|
|
|
|
|
<img src='https://cdn.acwing.com/media/article/image/2021/08/12/55909_f09eb023fb-IMG_6B91346846EE-1.jpeg'>
|
|
|
|
|
|
|
|
|
|
|
|
#### 闫氏$DP$分析法
|
|
|
|
|
|
**状态表示**—**集合**
|
|
|
$f[l][r]$:多边形的所有边【即：$(l,l+1),(1+1,l+2),...,(r-1,r),(l,r)$】划分成三角形的所有方案
|
|
|
|
|
|
**状态表示**—**属性**
|
|
|
$f[l][r]$:方案的最小费用
|
|
|
|
|
|
**状态计算**
|
|
|
|
|
|
>**其三个顶点的权值相乘都可得到一个权值乘积，试求所有三角形的顶点权值乘积之和至少为多少**。
|
|
|
|
|
|
所以代价是$\large w_l \times w_k \times w_j$,则状态转移方程：
|
|
|
|
|
|
$$\large 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} \approx 2\times {10}^{10}$
|
|
|
|
|
|
|
|
|
$long$ $long$ ：$9223372036854775807$ ,即$2^{63} \approx 9 \times {10}^{19}$
|
|
|
|
|
|
三个 $int$连乘就是 $2*{10}^{10}\times 2\times {10}^{10}\times 2\times {10}^{10}=8\times {10}^{30}$
|
|
|
|
|
|
$long$ $long$ 也是装不下，只能使用高精度(`__int128`也可以)
|
|
|
|
|
|
### 四、$\_\_int128$是个什么东东？
|
|
|
|
|
|
在关于$NOI$系列活动中编程语言使用限制的补充说明中表明:
|
|
|
|
|
|
> 允许使用以下划线开头的库函数或宏，但具有明确禁止操作的库函数和宏除外。
|
|
|
|
|
|
所以能在比赛中进行使用。
|
|
|
|
|
|
由于 $\_\_int128$ 仅仅是 ($GCC$) 编译器内的东西，不在 $(C++ 98/03/11/14/17/20)$ 标准内，
|
|
|
且仅 $(GCC4.6)$ 以上$64$位版本支持，很多配套都没有，只有四则运算功能。
|
|
|
|
|
|
目前$NOI$的$GCC$版本是$9.0$,放心使用~
|
|
|
|
|
|
[参考链接](https://www.bilibili.com/read/cv15945882)
|
|
|
[NOI Linux 2.0发布，将于9月1日起正式启用！](https://www.noi.cn/gynoi/jsgz/2021-07-16/732450.shtml)
|
|
|
|
|
|
#### 优点
|
|
|
|
|
|
$C++$内测的一种数据类型,$\_\_int128$的最大值是：
|
|
|
$\large ±85070591730234615865843651857942052864$,约为$\large 10^{38}$。
|
|
|
<font color='red' size=4><b>足够解决大部分高精度，大数据问题。</b></font>
|
|
|
|
|
|
#### 缺点
|
|
|
|
|
|
* 手写输入输出
|
|
|
|
|
|
|
|
|
### 五、区间$DP+\_\_int128$作法
|
|
|
```cpp {.line-numbers}
|
|
|
#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;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
### 六、$dfs+\_\_int128$解法
|
|
|
```cpp {.line-numbers}
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 50 + 10;
|
|
|
|
|
|
//__int128专用
|
|
|
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 w[N];
|
|
|
LL f[N][N];
|
|
|
|
|
|
// 计算[l,r]之间的三角剖分最大值
|
|
|
LL dfs(int l, int r) {
|
|
|
LL &v = f[l][r];
|
|
|
if (v != INF) return v; // 记忆化
|
|
|
if (r - l < 2) return v = 0; // 不够三个点，哪来的剖分值
|
|
|
for (int k = l + 1; k < r; k++) // 中间点k不能与l,r重合
|
|
|
v = min(v, dfs(l, k) + dfs(k, r) + w[l] * w[r] * w[k]);
|
|
|
return v;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
int n;
|
|
|
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++)
|
|
|
f[i][j] = INF;
|
|
|
|
|
|
write(dfs(1, n));
|
|
|
return 0;
|
|
|
}
|
|
|
```
|
|
|
|
|
|
### 七、高精度作法
|
|
|
```cpp {.line-numbers}
|
|
|
#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;
|
|
|
}
|
|
|
``` |
