题目链接：http://poj.org/problem?id=1651
思路：除了头尾两个数不能取之外，要求把所有的数取完，每取一个数都要花费这个数与相邻两个数乘积的代价，需要这个代价是最小的
用dp[i][j]表示区间[i,j]的最小代价，那么就有dp[i][j]=min(dp[i][k]+dp[k][j]+a[i]*a[k]*a[j]) i+1<=k<=j-1
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<vector>
#include<queue>
#include<iterator>
#include<vector>
#include<set>
#define dinf 0x3f3f3f3f
typedef long long ll; using namespace std; int a[],dp[][]; int main()
{
int num,i,j,k;
while(~scanf("%d",&num))
{
for(i=;i<num;i++)
scanf("%d",&a[i]);
for(i=;i<num-;i++)
dp[i][i+]=a[i]*a[i+]*a[i+];
int len;
for(len=;len<num;len++)
for(i=;i+len<num;i++)
{
j=i+len;
for(k=i+;k<j;k++)
{
if(dp[i][j]==)
dp[i][j]=dp[i][k]+dp[k][j]+a[i]*a[k]*a[j];
else
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[j]*a[k]);
}
}
printf("%d\n",dp[][num-]);
}
return ;
}