凸多边形的划分JAVA−BigInteger详细题解
这里附带打个广告——————我做的所有的题解
包括基础提高以及一些零散刷的各种各样的题
题目介绍
给定一个具有 N 个顶点的凸多边形,将顶点从 1 至 N 标号,每个顶点的权值都是一个正整数。
将这个凸多边形划分成 N−2 个互不相交的三角形,对于每个三角形,其三个顶点的权值相乘都可得到一个权值乘积,试求所有三角形的顶点权值乘积之和至少为多少。
输入格式
第一行包含整数 N,表示顶点数量。
第二行包含 N 个整数,依次为顶点 1 至顶点 N 的权值
输出格式
输出仅一行,为所有三角形的顶点权值乘积之和的最小值。
数据范围
N ≤ 50
数据保证所有顶点的权值都小于 10 ^ 9
输入样例:
5
121 122 123 245 231
输出样例:
12214884
1.算法细节
本题不是环形区间DP,是区间DP,因为不管以哪个点为起点不会改变形成三角形的个数和方案,并且这道题的代码和能量项链几乎一模一样
我的能量项链详细题解
题目的输入为这N个点的权值,假定我们用w[i] -> w[n]
来存储表示,这里从一个点的权值最大为10 ^ 9
,并且答案没有要求对一个数字取模,显然我们需要使用高精度,而JAVA中代表高精度的整数就是BigInteger
我们可以这么思考,使用闫式DP分析法,假定f[i][j]
代表这从点i
, i + 1
, ~, ~, ~, ~, ~, r - 1
, r
的顺序的点构成的多边形,其中相邻的点彼此连接,最后一条边r
连接到首点i
。在这个多边形中选取所有的各种各样的三角形的集合。而值代表着所得的所有三角形的顶点权值乘积之和的MIN最小值
。
从这个角度去看的话,那么该如何计算状态转移?
首先题目有一个很关键的条件,要求其中划分的为互不相交的三角形,我们可以这么想,任选端点k
,满足i < k < j
,和i
,j
这三个点构成三角形,原本的多边形被这个三角形分成三部分:1.三角形左边的多边形,2.三角形本身,3.三角形右边的多边形
因为有这个划分三角形不能相交的原则,我们可以用我们上面的集合划分的形式去表示这两个多边形内部划分三角形的顶点权值乘积之和的最小值
即f[i][k]
和f[k][j]
,那么f[i][j]
的状态转移的方式就是:f[i][j] = Min(f[i][j], f[i][k] + f[k][j] + w[i] * w[k] + w[j])
那么该如何思考区间DP的划分问题?
那么从构成一个三角形去考虑,len=3
的时候才能合并,故我们的len
从2开始枚举(为了初始化初值),以前的石子合并我们的枚举的k
满足条件为i <= k < j
,因为区间为1
的时候代表最小的单位,一个石子,所以可以划分区间为f[i][i]
为一个石子,然后f[i][i+1]
为最小的,两个石子合并。这道题应该是i < k < j
,因为三个点不同的时候才代表一个三角形,所以k
不能和i
相等。
求最小值,我们肯定需要将区间值f[i][j]
初始化为负无穷再去计算,而len
为2
的时候,即当j == i+1
的时候,肯定无法划分三角形,但是我们为了初始化当j == i + 2
即刚好构成三角形的时候,能做到初始化所有的刚好形成三角形的f[i][j]
为正好三个点的权值相乘,需要在len == 2
的时候,初始化这种f[i][j]
为0,这样len == 3
的时候转化:f[i][j] = Min(f[i][j], f[i][k] + f[k][j] + w[i] * w[k] + w[j])
就能把最基本的小三角形的值正确赋值。
为什么不像以前那样初始化MAX
为:0x3f3f3f3f
而是如下的
static String INF = "10000000000000000000000000000000";
我们设定无穷值,本身是为了防止非法状态转移,而这道题答案是高精度的,之前设定的0x3f3f3f3f
是Int
的最大值,这里为了防止答案都比最大值大,被设定的最大值污染答案,需要开的尽量大
2.具体代码
java BigInteger
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
public class Main {
static int n, N = 55;
static String INF = "10000000000000000000000000000000";
static BigInteger[][] f = new BigInteger[N][N];
static BigInteger[] a = new BigInteger[N];
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
n = Integer.parseInt(br.readLine());
String[] s1 = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
a[i + 1] = new BigInteger(s1[i]);
}
for (int len = 2; len <= n; len++) {
for (int i = 1, j; (j = i + len - 1) <= n; i++) {
if(len == 2) f[i][j] = new BigInteger("0");
else f[i][j] = new BigInteger(INF);
for (int k = i + 1; k < j; k++) {
f[i][j] = f[i][j].min(f[i][k].add(f[k][j]).add(a[i].multiply(a[k].multiply(a[j]))));
}
}
}
System.out.println(f[1][n]);
}
}
666,可以可以
嘿嘿,没有,俺很弱
你谦虚了