1069 凸多边形的划分（区间dp + 高精度）

梦里梦外; 2022-09-12 15:53 173阅读 0赞

**1. 问题描述：**

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

**输入格式**

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

**输出格式**

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

**数据范围**

N ≤ 50，  
数据保证所有顶点的权值都小于10 ^ 9

**输入样例：**

5  
121 122 123 245 231

**输出样例：**

12214884  
来源：[https://www.acwing.com/problem/content/description/1071/][https_www.acwing.com_problem_content_description_1071]

**2. 思路分析：**

这道题目思路上感觉还是挺难想的，我们可以通过画画图来发现其中的规律，可以发现当凸多边形中的某一条边确定之后那么由这条边划分的区域也就固定了，所以可以发现由一条边划分的两个区域就是相互独立的，这也是能够使用**区间dp**解决的一个重要特点，左边的区间如何决策不会影响到右边的区间，同理右边的区间如何决策也不会影响到左边的区间，所以我们可以考虑使用区间dp的思路来解决，通过画图可以发现我们可以将一个顶点到另外一个顶点之间的所有点看成是一个区间，区间中的某个点k与起点i和终点j各连一条线，那么就可以将凸多边形分为三个区域，其中这三部分是相互独立的，我们可以计算这三部分的值然后累加起来就是当前区间以k为分割点划分的凸多边形的值；区间dp也属于动态规划，而动态规划可以分为两个步骤：① 状态表示；② 状态计算；由上面的分析可以知道我们可以声明一个二维数组dp，其中dp\[L\]\[R\]表示将\[L，L + 1\]，\[L + 1，L + 2\]，...\[R - 1，R\]这个多边形划分为若干个三角形的最小权值和，状态计算对应集合的划分，我们可以枚举将区间划分为两个区间的分割点计算每一个集合的最小权值即可，可以发现这道题目的状态转移方程与320题能量项链的状态转移方程式一样的（题目的背景和分析的过程不太一样），由于这道题目不管是哪个点开始最终求解的结果都是一样的，所以这道题目不用转换为环形dp来解决；由于最终的数值最大为50 \* 10 ^ 9 \* 10 ^ 9 \* 10 ^ 9 > 10 ^ 28，所以如果使用c/c++来解决则需要写高精度，而python一般不会出现溢出的情况所以不写高精度也可以通过。下面是python的写法后面也加上了高精度的写法，我们可以先写出没有高精度的写法然后在计算结果的时候转换为高精度写法即可，可以在二维数组的基础上再加一维也即三维数组，其中前两维的含义与之前二维写法的含义是一样的，第三维用来存储当前区间的计算结果，也即第三维相当于是一维数组，因为数值最大比28位十进制大一点，所以第三维可以声明长度为35位即可，用来存储当前区间\[i，j\]的计算结果，我们可以将之前二维的状态转移方程中相关的操作使用高精度加法和乘法计算结果即可，使用一个辅助数组来存储临时的计算结果，最终将临时数组的结果复制到dp\[i:j\]即可。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

**因为python一般不会溢出，所以不写高精度也是可以通过的，对于其他语言的数据类型则需要写高精度，因为10 ^ 9 \* 10 ^ 9 \* 10 ^ 9 \* 50 > 10 ^ 28，不写高精度会造成溢出**

from typing import List
    
    # 高精度写法
    class Solution:
        # M为第三维存储的位数, 其中M = 35
        # 数组的高精度加法(因为dp数组的第三维是固定长度的, 所以这里使用数组形式的高精度加法和乘法会比较方便, 而列表在相加和相乘的时候长度是不固定的, 所以最终还需要处理一下长度问题不太方便)
        def add(self, a: List[int], b: List[int], M: int):
            c = [0] * M
            t = 0
            for i in range(M):
                t += a[i] + b[i]
                c[i] = t % 10
                t //= 10
            # 返回a与b每一位相加的结果
            return c
    
        # 高精度乘法
        def mul(self, a: List[int], b: int, M: int):
            c = [0] * M
            t = 0
            for i in range(M):
                t += a[i] * b
                c[i] = t % 10
                t //= 10
            return c
        
        # 高精度的按位比较
        def cmp(self, a: List[int], b: List[int], M: int):
            for i in range(M - 1, -1, -1):
                if a[i] > b[i]:
                    return 1
                elif a[i] < b[i]:
                    return -1
            return 0
        
        # 输出最终的结果
        def _print(self, a: List[int], M: int):
            k = M - 1
            # 过滤掉前导0
            while k >= 0 and a[k] == 0: k -= 1
            while k >= 0:
                print(a[k], end="")
                k -= 1
    
        def process(self):
            n = int(input())
            a = [0] + list(map(int, input().split()))
            # 这里声明三维数组最后一维用来存储计算的结果, 最后一维可以看成是一维数组, 存储结果
            M = 35
            dp = [[[0] * M for i in range(n + 1)] for j in range(n + 1)]
            for l in range(3, n + 1):
                i = 1
                while i + l - 1 <= n:
                    j = i + l - 1
                    dp[i][j][M - 1] = 1
                    for k in range(i + 1, j):
                        # 相当于是最后一位是1其余位是0, 也是第35位是1, 而最大所有权重加起来小于10 ^ 30所以这个数字可以看成是最大的
                        # 辅助数组用来计算dp表达式的结果
                        temp = [0] * M
                        temp[0] = a[i]
                        temp = self.mul(temp, a[k], M)
                        temp = self.mul(temp, a[j], M)
                        # 下面的dp[i][k], dp[k][j]相当于是一维数组
                        temp = self.add(temp, dp[i][k], M)
                        temp = self.add(temp, dp[k][j], M)
                        if self.cmp(dp[i][j], temp, M) > 0:
                            # 更新答案
                            dp[i][j] = temp[:]
                    i += 1
            # 输出结果
            self._print(dp[1][n], M)
    
    
    if __name__ == "__main__":
        # 创建一个类比较方便, 这样所有的方法都可以在一个类中操作
        Solution().process()

if __name__ == '__main__':
        # 其实python不用写高精度也是可以通过的, python一般没有溢出的概念
        n = int(input())
        # 在列表一开始的位置添加上0这个元素这样下标可以从1开始
        a = [0] + list(map(int, input().split()))
        # 注意这个数字要声明大一点, 因为相乘的结果可能是非常大的
        INF = 10 ** 35
        dp = [[0] * (n + 1) for i in range(n + 1)]
        for l in range(3, n + 1):
            i = 1
            while i + l - 1 <= n:
                j = i + l - 1
                dp[i][j] = INF
                for k in range(i + 1, j):
                    # 状态计算
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + a[i] * a[k] * a[j])
                i += 1
        print(dp[1][n])

[https_www.acwing.com_problem_content_description_1071]: https://www.acwing.com/problem/content/description/1071/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/818222db2dd0427587a9e50292b80fa6.png