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

代码

#include <bits/stdc++.h>using namespace std;const int N = 55, M = 35;typedef long long LL;int n;
LL temp[M], w[N];
LL f[N][N][M];void mul(LL a[], LL b)
{LL t = 0;for (int i = 0; i < M; i ++ ){t += a[i] * b;a[i] = t % 10;t /= 10;}
}void add(LL a[], LL b[])
{LL t = 0;for (int i = 0; i < M; i ++ ){t += a[i] + b[i];a[i] = t % 10;t /= 10;}
}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];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 ++ ){memset(temp, 0, sizeof temp);temp[0] = w[l];mul(temp, w[r]);mul(temp, w[k]);add(temp, f[l][k]);add(temp, f[k][r]);if (cmp(temp, f[l][r]) < 0)memcpy(f[l][r], temp, sizeof temp);}}}print(f[1][n]);return 0;
}