美文网首页
AcWing 1069. 凸多边形的划分 (区间dp+高精度)

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

作者: 来到了没有知识的荒原 | 来源:发表于2021-03-02 11:21 被阅读0次

    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;
    }
    

    相关文章

      网友评论

          本文标题:AcWing 1069. 凸多边形的划分 (区间dp+高精度)

          本文链接:https://www.haomeiwen.com/subject/wvptqltx.html