2132: 宝典2第十一章凸多边形三角划分

【题目描述】凸多边形三角划分（Triangle.cpp/c/pas) HNOI 1997

 张琪曼疑惑道：“墨老师，墨家学派的墨家宝库真的藏有对付天顶星人的方法？”

 墨老师：“是的，墨家学派的创始人是上古战国时代的墨子，那时墨子就已经对天文学、几何光学和静力学等进行了深入研究，比如说他认为物体的运动，在时间中表现为先后的差异，在空间中表现为位置的迁移，离开时空的运动是不存在的。又如对于物体的受力运动，提出作用力和反作用力，并认为如果没有阻力的话，物体会永远运动下去……”

 楚继光惊讶道：“这不是牛顿三定律里的内容吗？他能在上古时代就能想到，好强大。”

 墨老师：“虽然作为两大显学之一的墨家学派在后世日渐式微，但墨家精神和墨家传人一直传承到现在，我们现在要进入的墨家宝库就是其传人秘密建造的工程之一。”

　  张琪曼：“可是这个宝库打开的条件是：给定一个具有N（N<50）个顶点（从1到N编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N－2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？这应该怎么计算呢？”

【输入格式】

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

【输出格式】

第一行为最小的和的值，

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

【输入样例】

5

121 122 123 245 231

【输出样例】

　　12214884

    1 2 3，1 3 5，3 4 5