题目描述

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

输入格式

输入第一行为顶点数 n

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

输出格式

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

样例

样例输入

5 121 122 123 245 231

样例输出

12214884

数据范围与提示

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

题解

和能量项链那道题几乎一摸一样。不想说什么了

而且这道题还不用考虑环形

但是要注意每个数据过大，会爆long long 所以要开高精

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 55,M = 35;
const int INF = 0x3f3f3f3f;
#define vint vector<int>
typedef long long LL;
LL w[N];
vector<int> f[N][N];
int n;

vint add(vint &a, vint &b)
{
    vint c;
    for (int i = 0, t = 0; i < a.size() || i < b.size() || t; i++)
    {
        if (i < a.size()) t += a[i];
        if (i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

vint mul(vint &a, LL b)
{
    vint 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;
    }
    return c;
}

bool isgreater(vint a, vint b)
{
    if (a.size() != b.size()) return a.size() > b.size();
    return vint(a.rbegin(), a.rend()) > vint(b.rbegin(), b.rend());
}

int main()
{
    cin >> n;
    for(int i = 1;i <= n; ++ i) scanf("%lld",&w[i]);
    for(int len = 3; len <= n; ++ len)
      for(int l = 1; l + len - 1 <= n; ++ l)
      {
          int r = l + len - 1;
          f[l][r] = vint(35,9);
          for(int k = l + 1; k < r; ++ k)
          {
              vint temp(1, 1);
              temp = mul(temp, w[l]);
              temp = mul(temp, w[k]);
              temp = mul(temp, w[r]);
              temp = add(temp,f[l][k]);
              temp = add(temp,f[k][r]);
              if (isgreater(f[l][r], temp)) f[l][r] = temp;
          }
      }
      vint &v = f[1][n];
      for (int i = v.size() - 1; i >= 0; i--) printf("%d", v[i]);
     
      return 0;
}