10149. 「一本通 5.1 例 3」凸多边形的划分

题意

给定一个具有 $N$ 个顶点的凸多边形,将顶点从 $1$ 至 $N$ 标号,每个顶点的权值都是一个正整数。将这个凸多边形划分成 $N-2$ 个互不相交的三角形,试求这些三角形顶点的权值乘积和至少为多少。

思路

首先随便搞一个多边形:
然后给它顺时针每个顶点表上序号:
然后枚举$i,j$,要求:$i+1<j$,然后给$i,j$连一条线,分割出来另一个多边形:多边形23456
然后在$i,j$范围内枚举$k$,使得多边形23456又可以分割。
分割成如下图:
设$f[i][j]$表示把$i,j$的多边形切割成三角形后的权值乘积之和的最小值。 可得:
$$f[i][j]=min{f[i][k]+f[k][j]+a[i]a[j]a[k]}(0<i<j<k\leq n)$$
初始化:
$$f[i][j]=inf(0<i\leq n,0<j\leq n)$$ $$f[i][i+1]=0(0<i<n)$$ 时间复杂度:$O(n^3)$ 输出结果:$f[1][n]$ 当然,这道题范围特别大:对于 $100\%$ 的数据,有 $N\le 50$,每个点权值小于 $10^9$。三个数相乘最高可达$10^{27}$,所以需要使用高精度。这里使用了C++大数类,转自代号4101
暂无评论

发送评论


				
上一篇
下一篇