思路与算法

将顶点权值记为a[0..n-1]。可把相邻两个权值视为一块矩阵的行列维度，从而得到n-1个可依次相乘的矩阵。相邻矩阵链的每次合并代价，恰对应一个三角形的三个顶点权值乘积。

定义dp[l][r]为合并第l至第r个矩阵的最小代价。单个矩阵无需合并，dp[i][i]=0。枚举最后一次合并的位置k，转移为dp[l][k]+dp[k+1][r]+a[l]*a[k+1]*a[r+1]，在l≤k<r中取最小值。按区间长度递增计算，最终输出dp[0][n-2]。

本题结果可能超过64位。任意剖分含n-2≤48个三角形，每项小于10^27，所以答案小于48×10^27<2^96。参考程序使用本OJ的GCC C++11编译器支持的__int128扩展（并非ISO C++11标准整数类型），足以精确保存全部中间值，再逐位输出十进制。

正确性说明

固定多边形的一条边，每个剖分都唯一确定与这条边相邻的三角形及其第三个顶点，该三角形两侧又分别构成两个更小的凸多边形。反之，两侧各取一个合法剖分并加入这个三角形，就得到原多边形的一个合法剖分。

矩阵链最后一次合并的左右区间，恰对应上述两个子多边形，合并项a[l]*a[k+1]*a[r+1]就是中间三角形的代价。因此两种模型的分解和总代价一一对应。固定k后，两侧必须采用各自最优解，否则可替换成更优方案而降低总值。转移遍历全部k，且长度顺序保证所需子状态已最优，故最终状态是全局最小值。

复杂度

n个顶点。DP表分配并清零O(n²)，共有O(n²)个区间，每个枚举O(n)个分割点，总时间O(n³)，空间O(n²)。本题128位整数的运算视为固定宽度常数成本；十进制输出不足30位。

易错点

必须在第一次乘法前转成__int128，不能先让三个long long相乘再转换。矩阵数量为n-1，最终右端下标是n-2；合并项使用a[k+1]和a[r+1]。n=3只产生一个三角形。不能使用浮点数保存最优值，也不能用64位整数或过小的无穷大初始化。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using Wide = __int128;
void print(Wide x) {
    if (x >= 10)
        print(x / 10);
    cout << char('0' + x % 10);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> a(n);
    for (auto &x : a)
        cin >> x;
    vector<vector<Wide>> dp(n - 1, vector<Wide>(n - 1));
    for (int length = 2; length <= n - 1; ++length)
        for (int l = 0; l + length <= n - 1; ++l) {
            int rr = l + length - 1;
            dp[l][rr] = Wide(1) << 120;
            for (int k = l; k < rr; ++k)
                dp[l][rr] =
                    min(dp[l][rr], dp[l][k] + dp[k + 1][rr] + Wide(a[l]) * a[k + 1] * a[rr + 1]);
        }
    print(dp[0][n - 2]);
    cout << '\n';
}