題目 2476:
信息學(xué)奧賽一本通T1571-凸多邊形的劃分
時間限制: 2s
內(nèi)存限制: 192MB 提交: 85 解決: 30
題目描述
給定一個具有 N 個頂點的凸多邊形，將頂點從 1 至 N 標(biāo)號，每個頂點的權(quán)值都是一個正整數(shù)。將這個凸多邊形劃分成 N?2 個互不相交的三角形，試求這些三角形頂點的權(quán)值乘積和至少為多少。
輸入格式
輸入第一行為頂點數(shù) N
第二行依次為頂點 1 至頂點 N 的權(quán)值。
輸出格式
輸出僅一行，為這些三角形頂點的權(quán)值乘積和的最小值。
提示
數(shù)據(jù)范圍與提示：
對于 100% 的數(shù)據(jù)，有 N≤50，每個點權(quán)值小于 109 。