1069. Division of convex polygons (thinking, interval DP)

Limiting conditions ：

• It is divided into N-2 Triangles
• Disjoint  

analysis ：

Because a triangle needs three vertices , We can enumerate three vertices first , Then observe the nature

Pictured , When we show i,j,k Three vertices , At present, it can be divided into three sets

• Polygon set on the left + The polygon set on the right + Current triangle

It looks like an energy Necklace , By enumerating three points , Then calculate the set , Because we need to calculate the set of all individual triangles first   then   And then recurs to the weight of a whole polygon （ Enumerate two endpoints , At least one point in the middle , therefore len by 3, To ensure at least one point in the middle ）

therefore len At most from 3 Start enumeration , Because of n vertices , at most n Edge shape , So enumerate to n,3<=len<=n

We found that , Because different triangles cannot intersect , So for a polygon set

State means ： All by (i,i+1),(i+1,i+2)...(j-1,j) A collection of triangles divided by polygons

subset division / State calculation ： At present dp[i][j] It can be divided into three subsets = Polygon set on the left + Current triangle + Set of polygons on the right ,dp[i][j]=dp[i][k]+dp[k][j]+w[i]*w[i]*w[k], According to the break point k Can be divided into multiple subsets

• choice i+1 As a breakpoint
• ...
• choice j-1 As a breakpoint

Recursive order ：3<=len<=n

initialization ： infinity

The border ：dp[i][i]=dp[i][i+1]=0

Due to the need for high accuracy , So here we use vector Use high precision

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 55;
vector<int> dp[N][N];
int w[N];
typedef long long ll;
vector<int> init(ll a)
{
    if (a == (long long)1e18)
    {
        vector<int> res(35, 0);
        res.push_back(1);
        reverse(res.begin(), res.end());
        return res;
    }
    vector<int> res;
    while (a)
    {
        res.push_back(a % 10);
        a /= 10;
    }
    reverse(res.begin(), res.end());
    return res;
}
vector<int> add(vector<int> a, vector<int> b)
{
    vector<int> c;
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    int t = 0;
    for (int i = 0;i < a.size() || i < b.size();i++)
    {
        if (i < a.size())
            t += a[i];
        if (i < b.size())
            t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    if (t)
        c.push_back(t);
    reverse(c.begin(), c.end());
    return c;
}
vector<int> mul(vector<int> a, ll r)
{
    vector<int> c;
    reverse(a.begin(), a.end());
    ll t = 0;
    for (int i = 0;i < a.size() || t;i++)
    {
        if (i < a.size())
            t += a[i] * r;
        c.push_back(t % 10);
        t /= 10;
    }
    while (c.back() == 0 && c.size() > 1) c.pop_back();
    reverse(c.begin(), c.end());
    return c;
}
bool cmp(vector<int>& a, vector<int>& b)
{
    if (a.size() != b.size())
        return a.size() < b.size();
    else
        for (int i = 0;i < a.size();i++)
            if (a[i] != b[i])
                return a[i] < b[i];
    return false;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++)
        cin >> w[i];
    for (int i = 1;i <= n;i++)
        for (int j = 1;j <= n;j++)
            dp[i][j] = init((long long)1e18);

    for (int len = 1;len <= n;len++)
        for (int i = 1;i + len - 1 <= n;i++)
        {
            int j = i + len - 1;
            if (len == 1 || len == 2) dp[i][j] = init(0);
            else
                for (int k = i + 1;k < j;k++)
                {
                    auto temp = add(dp[i][k], dp[k][j]);
                    auto t = mul(mul(init(w[i]), w[j]), w[k]);
                    temp = add(temp, t);
                    
                    if (cmp(temp,dp[i][j]))
                        dp[i][j] = temp;
                }
        }
    for (auto t : dp[1][n])
        cout << t;
    return 0;
}