AcWing 1069. 凸多边形的划分
原题链接
中等
作者:
Adam_
,
2022-04-28 10:53:53
,
所有人可见
,
阅读 171
java高精度yyds(就是有点难写没有 c++的操作符重载
import java.util.*;
import java.math.BigInteger;
class Main {
static Scanner in = new Scanner(System.in);
static int n;
static BigInteger[] w;
static BigInteger[][] dp;
public static void main(String[] args) {
read();
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
dp[i][j] = new BigInteger("0");
for(int len = 3; len <= n; ++len) {
for(int l = 1; l + len - 1 <= n; ++l) {
int r = l + len - 1;
dp[l][r] = new BigInteger("100000000000000000000000000000000000");
for(int k = l + 1; k < r; ++k)
dp[l][r] = dp[l][r].min(dp[l][k].add(dp[k][r].add(w[l].multiply(w[k].multiply(w[r])))));
}
}
System.out.println(dp[1][n]);
}
static void read() {
n = in.nextInt();
w = new BigInteger[n + 1];
dp = new BigInteger[n + 1][n + 1];
for(int i = 1; i <= n; ++i)
w[i] = new BigInteger(in.nextInt() + "");
}
}