问题链接：
http://acm.upc.edu.cn/OnlineJudge/problem.php?cid=1008&pid=0

这是一个经典题目"凸多边形最优三角形剖分",解法是区间dp。 dp[i][j] 表示从第i到第j个点最优剖分 的答案。 当 j=i 或 j=i+1 时，无法构成三角形， dp[i][j]=0 。 当 j>=i+2 时，考虑一个分割点k, ijk 三点构成一个三角形，此时划分为i到k部分，k到j部分，以及三角形ijk部分这三个部分。i到k部分和k到j 部分是子问题，可以利用之前求出的结果，三角形ijk的值是三点权值之积。 

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
using namespace std;
int a[1000];
int dp[1005][1005];
int cos(int x,int y,int z)
{
    return a[x]*a[y]*a[z];
}
int main ()
{
    int T;
    cin >> T;
    for (int I=1;I<=T;I++)
    {
        int n;
        cin >> n;
        for (int i=1;i<=100;i++)
        {
            for (int j=1;j<=100;j++)
            {
                dp[i][j]=0;
            }
        }
        for (int i=1;i<=n;i++)
        {
            a[i]=0;
        }
        for (int i=1;i<=n;i++)
        {
            cin >> a[i];
        }
        for (int i=n-2;i>=1;i--)              //从后往前找
        {
            for (int j=i+2;j<=n;j++)          //每次从最少三个点找起
            {
                for (int k=i+1;k<=j-1;k++)。  //k不能去I或j,分成三部分，ij部分，jk部分，ijk三角形部分
                {
                    dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+cos(i,j,k));
                }
            }
        }
        cout << "Case #" << I << ": " << dp[1][n] << endl;


    }
    return 0;
}