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
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇