Description
给定一个具有n(n<=50)个顶点(从1到n编号)的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成n-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？
Input
第一行为顶点数n，第二行为n个顶点（从1到n）的权值(均小于longint)。
Output
只有一行为最小的和的值。
Sample Input
5
121 122 123 245 231
Sample Output
12214884
【参考程序】：
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long array[60];
array F[110][110],a,s1,s2,s3;
long long n;
void mark(array &c)
{
for (int i=1;i<=c[0];i++)
{
c[i+1]+=c[i]/100000;
c[i]%=100000;
}
while (c[c[0]+1])
{
c[0]++;
c[c[0]+1]+=c[c[0]]/100000;
c[c[0]]%=100000;
}
}
void mul(long long a1,long long a2,long long a3,array &c)
{
memset(c,0,sizeof(c));
c[0]=c[1]=1;
for (int i=1;i<=c[0];i++) c[i]*=a1;
mark(c);
for (int i=1;i<=c[0];i++) c[i]*=a2;
mark(c);
for (int i=1;i<=c[0];i++) c[i]*=a3;
mark(c);
}
void add(array a,array b,array &c)
{
memset(c,0,sizeof(c));
if (a[0]>b[0]) c[0]=a[0];
else c[0]=b[0];
for (int i=1;i<=c[0];i++) c[i]=a[i]+b[i];
mark(c);
}
bool check(array a,array b)
{
if (a[0]<b[0]) return false;
if (a[0]>b[0]) return true;
for (int i=a[0];i>=1;i--)
if (a[i]<b[i]) return false;
else if (a[i]>b[i]) return true;
return false;
}
int main()
{
//freopen("data5.in","r",stdin);
//freopen("data5.out","w",stdout);
scanf("%lld",&n);
for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
F[i][j][0]=1;
for (int i=n-2;i>=1;i--)
for (int j=i+2;j<=n;j++)
{
F[i][j][0]=60;
for (int k=i+1;k<=j-1;k++)
{
mul(a[i],a[k],a[j],s1);
add(F[i][k],F[k][j],s2);
add(s1,s2,s3);
if (check(F[i][j],s3))
memcpy(F[i][j],s3,sizeof(F[i][j]));
}
}
printf("%lld",F[1][n][F[1][n][0]]);
for (int i=F[1][n][0]-1;i>=1;i--) printf("%05lld",F[1][n][i]);
printf("\n");
return 0;
}