题解 | #凸多边形的划分#

凸多边形的划分 (nowcoder.com)

转移方程：

状态表示：

​ F(i,j)表示区间i到j的最小价值

边界：

目标：

代码：

import math
f = [[math.inf] * 154 for _ in range(154)]
n = int(input())
a = [0 for _ in range(2 * n + 12)]

arr = list(map(int, input().split()))

for i in range(1, n + 1):
    a[i] = arr[i-1]
    a[i + n] = a[i]

for i in range(1, 2 * n + 1):
    f[i][i] = a[i]
    f[i][i + 1] = 0

for len in range(2, n + 1):
    for i in range(1, 2 * n - len + 1 + 1):
        j = i + len - 1
        for k in range(i+1,j):
            f[i][j] = min(f[i][j], f[i][k] + f[k][j] + a[i] * a[j] * a[k])

mi = math.inf
for i in range(1,n + 1):
    mi = min(mi, f[i][i + n - 1])
print(mi)

总结：与能量项链相同，只不过是求最小值。