凸多边形的划分
提交数: 214, 通过率: 28.5%, 平均分: 49.39
题目描述:
给定一个具有N（N<=50）个顶点（从1到N编号）的凸多边形，每个顶点的权均是一个正整数。问：如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？
输入格式:
第一行为顶点数N，第二行为N个顶点（从1到N）的权值。
输出格式:
只有一行为这些三角形顶点的权的乘积之和的最小值。
样例输入:
5 121 122 123 245 231
样例输出:
12214884
提示:
注意每个顶点均为long long范围内的正整数，建议使用 __int128类型。
时间限制: 1000ms空间限制: 256MB