E题题解

区间DP，要用高精。
我不会写高精，比赛python不太熟，调了半天最后都没有调出来。
补一发题解。

思路：凸边形，取两个点，形成的一条边，我们把那条边形成的多边形中按顺序取点，区间DP。
（好像说的有点抽象，看图就行）

转移式：f[i][j] = min(f[i][j], f[i][k] + f[k][j] + a[i] * a[j] * a[k])

代码如下：

a = []
T = int(input())
f = [([99999999999999999999999999999] * (T+10)) for i in range(T+10)]
for case in range(T):
    num = list(map(int, input().split()))
    for i in num:
        a.append(i)
    for i in range(T):
            f[i][i+1] = 0
    for t in range(2, T):
        for i in range(0, T-t):
            j = i + t
            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])
    print(f[0][T-1], end="")
    exit()