AcWing 1069. 凸多边形的划分 (区间dp+高精度)

AcWing 1069. 凸多边形的划分

非高精度写法

数据范围小这个就可以过了

#include<bits/stdc++.h>

using namespace std;
const int N = 55;
int w[N];
int f[N][N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        w[i + n] = w[i];
    }

    for (int len = 3; len <= n; len++) {
        for (int i = 1; i+len-1 <= n; i++) {
            int j = i + len - 1;
            f[i][j] = 1e9;
            for (int k = i + 1; k < j; k++) {
                f[i][j] = min(f[i][j], f[i][k] + f[k][j] + w[i] * w[j] * w[k]);
            }
        }
    }

    cout<<f[1][n];

    return 0;
}

高精度乘法+高精度加法

static LL c[M];是为了每次调用 mul 或 add ，不用开辟新的c数组，节省空间

#include<bits/stdc++.h>

typedef long long LL;

using namespace std;
const int N = 55, M = 35;
LL w[N];
LL f[N][N][M];
LL temp[M];

void mul(LL a[], LL b) {
    static LL c[M];
    memset(c, 0, sizeof c);
    LL t = 0;
    for (int i = 0; i < M; i++) {
        t += a[i] * b;
        c[i] = t % 10;
        t /= 10;
    }
    memcpy(a, c, sizeof c);
}

void add(LL a[], LL b[]) {
    static LL c[M];
    memset(c, 0, sizeof c);
    for (int i = 0, t = 0; i < M; i++) {
        t += a[i] + b[i];
        c[i] = t % 10;
        t /= 10;
    }
    memcpy(a, c, sizeof c);

}

int cmp(LL a[], LL b[]) {
    for (int i = M - 1; i >= 0; i--) {
        if (a[i] != b[i])return a[i] > b[i] ? 1 : -1;
    }
    return 0;
}

void print(LL a[]) {
    int k = M - 1;
    while (k && !a[k])k--;
    while (k >= 0)cout << a[k--];
    cout << endl;
}

int main() {
    freopen("data.txt", "r", stdin);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
        w[i + n] = w[i];
    }

    for (int len = 3; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            f[i][j][M - 1] = 1; // f[i][j]设为INF

            for (int k = i + 1; k < j; k++) {
                memset(temp, 0, sizeof temp);

                temp[0] = w[i];
                mul(temp, w[j]);
                mul(temp, w[k]);
                add(temp, f[i][k]);
                add(temp, f[k][j]);

                if (cmp(f[i][j], temp) > 0) {
                    memcpy(f[i][j], temp, sizeof temp);
                }
//              f[i][j] = min(f[i][j], f[i][k] + f[k][j] + w[i] * w[j] * w[k]);
            }
        }
    }

    print(f[1][n]);

    return 0;
}