AcWing 1069. 凸多边形的划分

题目传送门

一、题意分析

二、朴素做法

#include 

using namespace std;
const int N = 55;
const int INF = 0x3f3f3f3f;
int n;
int w[N];
int f[N][N];

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> 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] = INF;      //预求最小，先设最大
            for (int k = l + 1; k < r; k++)//枚举第三点
                f[l][r] = min(f[l][r], f[l][k] + f[k][r] + w[l] * w[k] * w[r]);
        }
    //输出
    printf("%d", f[1][n]);
    return 0;
}

三、正规做法

#include

using namespace std;
typedef long long LL;
const int N = 55;
int n;              //n个顶点
int w[N];           //每个点的权重
vector f[N][N];//高精度存储最后的结果值

//对比两个高精度的大小
bool cmp(vector A, vector B) {
    if (B.size() == 0) return true;
    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;
}

//高精加高精
vector add(vector A, vector B) {
    if (A.size() < B.size()) return add(B, A);
    vector 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;
    }
    while (t) c.push_back(t % 10), t /= 10;
    return c;
}

//乘法高精*低精
vector mul(vector a, LL b) {
    vector c;
    LL t = 0;
    for (int i = 0; i < a.size(); i++) {
        t += b * a[i];
        c.push_back(t % 10);
        t /= 10;
    }
    while (t) c.push_back(t % 10), t /= 10;
    return c;
}

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> w[i];

    //区间DP
    //此处初始状态f[l][l+1] = 0 初始就是空vector，不用额外设置
    for (int len = 3; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            //初始化初始状态
            for (int k = l + 1; k < r; ++k) {
                //三个顶点权值相乘
                vector v = mul(mul({w[l]}, w[k]), w[r]);
                //DP值相加
                v = add(add(f[k][r], f[l][k]), v);
                //是不是可以迁移
                if (cmp(v, f[l][r])) f[l][r] = v;
            }
        }
    }
    //输出最终答案
    vector res = f[1][n];
    //倒序输出
    for (int i = res.size() - 1; i >= 0; i--) printf("%d", res[i]);
    return 0;
}