AcWing 1069. 凸多边形的划分

题目传送门

一、算法思路

这是一个经典的图形学 问题 — 三角剖分

因为我们现实中常见的一些 多边形图形 存储到计算机中，需要转存为一个个 像素点

那么如何存储一个 多边形 最简单的方案就是把它转化为 多个三角形 进行存储

也就是 三角剖分 问题，不只是 凸多边形，还能解决 凹多边形， 有孔多边形 等问题

回归本题，本题是一个给定的 凸多边形 求 三角剖分 的最小费用方案

很显然一个 凸多边形的剖分方案 并不唯一：

在 选定 多边形中 两个点 后，找出 三角形 的 第三个点 的方案有 \(n−2\) 个

然后还要分别 **划分** 他的 **左右两块区域**

闫氏\(DP\)分析法

状态表示—集合\(f_{l,r}\):当前划分到的多边形的左端点是 \(l\)，右端点是 \(r\) 的方案
状态表示—属性\(f_{l,r}\):方案的费用最小
状态计算—\(f_{l,r}\):

\(f_{l,r}=min(f_{l,k}+f_{k,r}+w_l×w_k×w_r)(l<k<r)\)

区间DP 在状态计算的时候一定要 认真 划分好 边界 和 转移，对于不同题目是不一样的

然后本题非常的嚣张，直接用样例的 \(5\) 的点告诉我们答案会爆 \(int\) 和 \(long\) \(long\)

并且没有 取模 要求，那就只能上 高精度 了,要是懒的话，那用一下__int128,这个是yyds

二、数据范围

本题因为是三个\(10^9\)的数字相乘为最大值范围:

\(int :2147483648\),即\(2e10\)

\(long\) \(long\) ：\(9223372036854775807\) \(9*e19\)

三个 \(int\)连乘就是 \(2e10*2e10*2e10=8*e30\)

\(long\) \(long\) 也是装不下，只能使用高精度(__int128也可以)

三、朴素做法

#include <bits/stdc++.h>

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

int main() {
    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;
}

四、int128作法

#include<bits/stdc++.h>

using namespace std;
/**
 __int128 就是占用128字节的整数存储类型。由于是二进制，范围就是 (-2^{127}) ~ (2^{127}-1)，
 如果使用了 unsigned __int128，则范围变成 (0) ~ (2^{128})，即约39位数！

 由于 __int128 仅仅是 (GCC) 编译器内的东西，不在 (C++ 98/03/11/14/17/20) 标准内，
 且仅 (GCC4.6) 以上64位版本支持，很多配套都没有，只有四则运算功能
 所以要自己写输入输出。使用方法与 int long long 无异
 */
typedef unsigned __int128 LL;
const LL INF = 1e38;

LL read() {
    LL x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void print(LL x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

const int N = 55;
LL f[N][N];
LL w[N];


int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) w[i] = read();
    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]);
        }
    }
    print(f[1][n]);
    return 0;
}

五、高精度作法

#include<bits/stdc++.h>

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

//对比两个高精度的大小
bool cmp(vector<int> A, vector<int> 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<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 < 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<int> mul(vector<int> a, LL b) {
    vector<int> 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<int> 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<int> res = f[1][n];
    //倒序输出
    for (int i = res.size() - 1; i >= 0; i--) printf("%d", res[i]);
    return 0;
}

六、dfs+int128解法

#include <bits/stdc++.h>

using namespace std;
typedef unsigned __int128 LL;
const LL INF = 1e38;
const int N = 50 + 10;
LL a[N];
LL g[N][N];

LL read() {
    LL x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void print(LL x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}


LL dfs(int i, int j) {
    if (j - i <= 1) return g[i][j] = 0;
    if (g[i][j] != INF) return g[i][j];
    LL sum = a[i] * a[j];
    for (int k = i + 1; k < j; ++k)
        g[i][j] = min(g[i][j], dfs(i, k) + dfs(k, j) + sum * a[k]);

    return g[i][j];
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) a[i] = read();
    //int128的初始化极值，还是老老实实的用for循环吧
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; ++j)
            g[i][j] = INF;

    print(dfs(1, n));
    return 0;
}