C/C++教程

[AcWing 1069] 凸多边形的划分

本文主要是介绍[AcWing 1069] 凸多边形的划分，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

image

点击查看代码 
#include<iostream>
#include<cstring>

using namespace std;

typedef long long LL;

const int N = 60, M = 50;

int n;
int w[N];
LL f[N][N][M];

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

void mul(LL a[], LL b)
{
    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);
}

int cmp(LL a[], LL b[])
{
    for (int i = M - 1; i >= 0; i --) {
        if (a[i] > b[i])
            return 1;
        else if (a[i] < b[i])
            return -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()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> w[i];
    LL tmp[M];
    for (int len = 3; len <= n; len ++) {
        for (int l = 1; l + len - 1 <= n; l ++) {
            int r = l + len - 1;
            f[l][r][M - 1] = 1;
            for (int k = l + 1; k < r; k ++) {
                int t = w[l];
                for (int i = 0; i < M; i ++) {
                    tmp[i] = t % 10;
                    t /= 10;
                }
                mul(tmp, w[k]);
                mul(tmp, w[r]);
                add(tmp, f[l][k]);
                add(tmp, f[k][r]);
                if (cmp(tmp, f[l][r]) < 0)
                    memcpy(f[l][r], tmp, sizeof tmp);
            }
        }
    }
    print(f[1][n]);
    return 0;
}
  1. 状态表示
    \(f[l][r]\) 表示将顶点 \([l,r]\) 划分成三角形的所有方案的最大值
  2. 状态计算
    用 \(k\) 表示 \((l,r)\) 中的一点
    \(f[l][r] = min(f[l][k] + f[k][r] + w[l] \cdot w[k] \cdot w[r])\)
  3. 高精度写法
这篇关于[AcWing 1069] 凸多边形的划分的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航