凸多边形的划分

凸多边形的划分 (链2)

题目描述

给定一个具有 $N$ 个顶点的凸多边形，将顶点从 $1$ 至 $N$ 标号，每个顶点的权值都是一个正整数。将这个凸多边形划分成 $N-2$ 个互不相交的三角形，试求这些三角形顶点的权值乘积和至少为多少。

输入格式

输入第一行为顶点数 $N$

第二行依次为顶点 $1$ 至顶点 $N$ 的权值。

输出格式

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

输入样例

5
121 122 123 245 231

输出样例

12214884

提示

对于 $100 \%$ 的数据，有 $N \leq 50$ ，每个点权值小于 $10^9$ 。

思路

const int N = 110;
vector<int> INF(30, 9);
vector<vector<int>> v(2 * N);
vector<vector<vector<int>>> dp(2 * N, vector<vector<int>>(2 * N, INF));

bool cmp(vector<int> a, vector<int> b)
{
    int n = a.size(), m = b.size();
    if (n != m) return n < m;
    for (int i=n-1;i>=0;i--)
    {
        if (a[i] == b[i])   continue;
        else    return a[i] < b[i];
    }
    return false;
}

void print(vector<int> a)
{
    a = vector<int>(rall(a));
    for (auto di : a)   cout << di;
    cout << _endl;
}

vector<int> add(vector<int> a, vector<int> b)
{
    if (cmp(a, b))  swap(a, b);

    int n = a.size(), m = b.size();
    vector<int> c(n + 1, 0);
    for (int i=0;i<n;i++)
    {
        c[i] += a[i];
        if (i < m)  c[i] += b[i];
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    while (!c.back() && c.size() > 1)   c.pop_back();
    return c;
}

vector<int> mul(vector<int> a, vector<int> b)
{
    if (cmp(a, b))  swap(a, b);

    int n = a.size(), m = b.size();
    vector<int> c(n + m + 1, 0);
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<m;j++)
        {
            c[i + j] += a[i] * b[j];
            c[i + j + 1] += c[i + j] / 10;
            c[i + j] %= 10;
        }
    }
    while (!c.back() && c.size() > 1)   c.pop_back();
    return c;
}

vector<int> work(int l, int r)
{
    if (r - l + 1 <= 2) return vector<int>(1, 0);
    if (dp[l][r] != INF)   return dp[l][r];

    for (int i=l+1;i<r;i++)
    {
        auto pa = work(l, i);
        auto pb = work(i, r);
        auto pc = mul(mul(v[l], v[i]), v[r]);
        auto res = add(add(pa, pb), pc);
        if (!cmp(dp[l][r], res))
            dp[l][r] = res;
    }
    return dp[l][r];
}

void solve()
{
    int n;  cin >> n;
    string s;
    for (int i=1;i<=n;i++)
    {
        cin >> s;
        s = string(rall(s));
        for (auto ch : s)
            v[i].push_back(ch - '0');
        v[i + n] = v[i];
    }

    auto ans = work(1, n);
    print(ans);
}