<—点个赞吧QwQ

宣传一下算法提高课整理

给定一个具有 $N$ 个顶点的凸多边形，将顶点从 $1$ 至 $N$ 标号，每个顶点的权值都是一个正整数。

将这个凸多边形划分成 $N-2$ 个互不相交的三角形，对于每个三角形，其三个顶点的权值相乘都可得到一个权值乘积，试求所有三角形的顶点权值乘积之和至少为多少。

输入格式

第一行包含整数 $N$，表示顶点数量。

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

输出格式

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

数据范围

$N \le 50$,
数据保证所有顶点的权值都小于$10^9$

输入样例：

5
121 122 123 245 231

输出样例：

12214884

思路

闫氏$\text{DP}$分析法：
状态表示：$f_{i,j}$

• 集合：$i\sim j$中的所有点组成的多边形分成最多的三角形所需要的最小权值
• 属性：$\min$

状态计算

• 我们以第$i+1$个点为分界点，所需要的权值为$f_{i,i+1} + f_{i+1,j} + a_i\times a_{i+1} \times a_j$
• 以第$i+2$个点为分界点，所需要的权值为$f_{i,i+2} + f_{i+2,j} + a_i\times a_{i+2} \times a_j$
• 以第$k$个点为分界点，所需要的权值为$f_{i,k} + f_{k,j} + a_i\times a_{k} \times a_j$
• 所以状态状态转移方程就是$f_{i,j}=\underset{k\in [i+1,j-1]}\min{\{ f_{i,k} + f_{k,j} + a_i\times a_{k} \times a_j\}}$

初始状态：$f_{i,i}(i\in [1,n])$以及$f_{i,i+1}(i \in [1,n-1])$
目标状态：$f_{1,n}$

这里介绍一个好东西：_int128
它支持运算，且是 $128$ 位的，只是不支持输出，所以。。。得手写啊啊啊

代码

#include <iostream>
using namespace std;
typedef __int128 LL;
const int N = 60;
int n;
int a[N];
LL f[N][N];
ostream &operator << (ostream &out,LL x) {
    if (!x) {
        out << 0;
        return out;
    }
    int stk[110],top = 0;
    while (x) stk[++top] = x % 10,x /= 10;
    for (int i = top;i >= 1;i--) out << stk[i];
    return out;
}
int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int len = 3;len <= n;len++) {
        for (int i = 1;i + len - 1 <= n;i++) {
            int j = i + len - 1;
            f[i][j] = 1e126;
            for (int k = i + 1;k <= j - 1;k++) f[i][j] = min (f[i][j],f[i][k] + f[k][j] + (LL)a[i] * a[k] * a[j]);
        }
    }
    cout << f[1][n] << endl;
    return 0;
}