306009 - 凸多边形三角划分

给定一个具有N（N＜50）个顶点（从1到N编号）的凸多边形，每个顶点的权值均已知。问如何把这个凸多边形划分成N－2个互不相交的三角形，使得这些三角形顶点的权值的乘积之和最小？

第一行为顶点数N，第二行为 N个顶点（从1到N）的权值。

第一行为最小的和的值。

第二行为各三角形组成的方式。各三角形各顶点之间以空格间隔，顶点从小到大排序，三角形之间从左到右按字典序排序，中间的逗号为半角字符，注意答案非唯一。