1069. 凸多边形的划分

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

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

输入格式

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

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

输出格式

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

数据范围

N≤50,
数据保证所有顶点的权值都小于109

输入样例：

5
121 122 123 245 231

输出样例：

12214884

思路：

/*
f[l][r]表示多边形的所有边【即：(l,l+1),(1+1,l+2),...,(r-1,r),(l,r)】划分成三角形的所有方案的最小值根据状态方程的定义，结合图形，枚举区间的分隔点最后得到的就是两个区间：f[l][k]和f[k][r]，还有一个三角形，它的顶点分别是w[l],w[k],w[r]
最终的状态转移方程：f[l][r] = min(f[l][r],f[l][k] + f[k][r] + w[l] * w[k] * w[r])
*/

代码：

// 链式dp 随便选一条边都可以#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 55, M = 35;
vector<int> f[N][N];
int w[N];
int n;
vector<int> add(vector<int> &A, vector<int> &B)
{if (A.size() < B.size())return add(B, A);vector<int> C;int t = 0;for (int i = 0; i < A.size(); i++){t += A[i];if (i < B.size())t += B[i];C.push_back(t % 10);t /= 10;}if (t)C.push_back(t);return C;
}vector<int> mul(vector<int> &A, LL b)
{vector<int> C;LL t = 0;for (int i = 0; i < A.size() || t; i++){if (i < A.size())t += A[i] * b;C.push_back(t % 10);t /= 10;}while (C.size() > 1 & C.back() == 0)C.pop_back();return C;
}bool cmp(vector<int> &A, vector<int> &B)
{if (A.size() != B.size())return A.size() > B.size();for (int i = A.size() - 1; i >= 0; i--)if (A[i] != B[i])return A[i] > B[i];return true;
}int main()
{cin >> n;for (int i = 1; i <= n; i++)cin >> w[i];for (int L = 3; L <= n; L++){for (int i = 1; i + L - 1 <= n; i++){int j = i + L - 1;f[i][j].resize(M, 1);for (int k = i + 1; k < j; k++){vector<int> temp;temp.push_back(w[i]);temp = mul(temp, w[k]);temp = mul(temp, w[j]);temp = add(temp, f[i][k]);temp = add(temp, f[k][j]);if (cmp(f[i][j], temp))f[i][j] = temp;}}}for (int i = f[1][n].size() - 1; i >= 0; i--)cout << f[1][n][i];return 0;
}