题目描述

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

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

输入格式
第一行包含整数 N，表示顶点数量。

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

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

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

样例

输入样例：
5
121 122 123 245 231
输出样例：
12214884
难度：中等
时/空限制：1s / 64MB
总通过数：1026
总尝试数：2134
来源：《信息学奥赛一本通》
算法标签

算法1

C++ 代码

#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<(int)a.size();i++)
    {
        t+=a[i];
        if(i<(int)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, int b)
{
    vector<int> c;
    LL t=0;
    for(int i=0;i<(int)a.size()||t; i++)
    {
        if(i<(int)a.size()) t+=(LL)a[i]*b;
        c.push_back(t%10);
        t/=10;
    }
    return c;
}
bool cmp(vector<int>& a, vector<int>& b)
{
    if(a.size()!=b.size()) return a.size()>b.size();
    int i=(int)a.size()-1;
    while(a[i]==b[i]&&i>0) i--;
    return a[i]>b[i];
}
int main()
{
    cin>>n;
    for(int i=1;i<=n; i++) cin>>w[i];
    vector<int> tmp;
    for(int len=3;len<=n;len++)
    {
        for(int l=1;l+len-1<=n;l++)
        {
            int r=l+len-1;
            f[l][r]=vector<int>(M,1);
            for(int k=l+1;k<r;k++)
            {
                tmp.clear();
                tmp.push_back(w[l]);
                tmp=mul(tmp,w[k]),tmp=mul(tmp,w[r]);
                tmp=add(tmp,f[l][k]),tmp=add(tmp,f[k][r]);
                if(cmp(f[l][r],tmp)) 
                    f[l][r]=tmp;
            }
        }
    }
    for(int i=f[1][n].size()-1;i>=0;--i)
    {
        cout<<f[1][n][i];
    }
    cout<<endl;
}