H. 多边形的三角划分

传统题

1000ms

128MiB

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

说明

N个顶点的凸多边形[顶点顺序为1->N]，各顶点权值已知，要求划分成N-2个三角形，使各三角形顶点权值乘积之和为最小当n=4，各顶点的权值分别为10,5,7,6时，所求最小值为10*5*6+5*6*7=510。

第一行：一个整数n 第二行：n个整数,依次表示各顶点的权值

一个整数表示最小的乘积之和

4
10 5 7 6

n<=200,所有输入数据均<=1000,所求得的最小值小于10的9次方。