#468. 凸多边形的划分

凸多边形的划分

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

输入格式

输入第一行为顶点数N\red{N}

第二行依次为顶点1\red{1}至顶点N\red{N}的权值。

输出格式

输出仅一行,为这些三角形顶点的权值乘积和的最小值。

样例

输入数据

5
121 122 123 245 231

输出数据

12214884

提示

对于100%\red{100\%}的数据,有 N50\red{N≤50},每个点权值小于109\red{10^9}

周六集训队区间DP

未参加
状态
已结束
规则
IOI
题目
6
开始于
2023-4-8 15:15
结束于
2023-4-12 19:15
持续时间
100 小时
主持人
参赛人数
29