算法提高 矩阵乘法时间限制：3.0s 内存限制：256.0MB问题描述有n个矩阵，大小分别为a0*a1, a1*a2, a2*a3, ..., a[n-1]*a[n]，现要将它们依次相乘，只能使用结合率，求最少需要多少次运算。
两个大小分别为p*q和q*r的矩阵相乘时的运算次数计为p*q*r。输入格式输入的第一行包含一个整数n，表示矩阵的个数。
第二行包含n+1个数，表示给定的矩阵。输出格式输出一个整数，表示最少的运算次数。样例输入3
1 10 5 20样例输出150数据规模和约定1<=n<=1000, 1<=ai<=10000。
题目链接：
http://lx.lanqiao.cn/problem.page?gpid=T417
题目大意：
给一个矩阵链乘，只能加括号，问最小矩阵运算次数。
题目思路：
【区间DP】
f[i][j]表示i~j的最小代价，枚举拆分点k,f[i][j]=min(f[i][k]+f[k][j]+a[i]*a[k]*a[j])
/****************************************************
Author : Coolxxx
Copyright 2017 by Coolxxx. All rights reserved.
BLOG : http://blog.csdn.net/u010568270
****************************************************/
#include<bits/stdc++.h>
#pragma comment(linker,"/STACK:1024000000,1024000000")
#define abs(a) ((a)>0?(a):(-(a)))
#define lowbit(a) (a&(-a))
#define sqr(a) ((a)*(a))
#define mem(a,b) memset(a,b,sizeof(a))
const double eps=1e-;
const int J=;
const int mod=;
const int MAX=0x7f7f7f7f;
const double PI=3.14159265358979323;
const int N=;
using namespace std;
typedef long long LL;
double anss;
LL aans;
int cas,cass;
int n,m,lll,ans;
LL a[N];
LL f[N][N];
int main()
{
#ifndef ONLINE_JUDGE
// freopen("1.txt","r",stdin);
// freopen("2.txt","w",stdout);
#endif
int i,j,k,l;
int x,y,z;
// for(scanf("%d",&cass);cass;cass--)
// for(scanf("%d",&cas),cass=1;cass<=cas;cass++)
// while(~scanf("%s",s))
while(~scanf("%d",&n))
{
mem(f,0x7f);
for(i=;i<=n+;i++)
scanf("%lld",&a[i]);
for(k=;k<=n;k++)f[k][k+]=;
for(l=;l<=n;l++)
{
for(i=;i+l<=n+;i++)
{
j=i+l;
for(k=i+;k<j;k++)
{
f[i][j]=min(f[i][j],f[i][k]+f[k][j]+a[i]*a[k]*a[j]);
}
}
}
printf("%lld\n",f[][n+]);
}
return ;
}
/*
//
//
*/