[数据结构与算法]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;
}