题目地址：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1600
区间DP入门题
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(int)(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(int)(b);--i)
const int INF=0x3f3f3f3f;
int n,p[100+5],d[100+5][100+5];
int DP(int i,int j){int& ans=d[i][j];if(ans!=-1) return ans;if(i==j) return ans=0;ans=INF;REP(k,i,j) ans=min(ans,DP(i,k)+DP(k+1,j)+p[i]*p[k+1]*p[j+1]);return ans;
}
int main(int argc, char const *argv[])
{int T; scanf("%d",&T);while(T--&&scanf("%d",&n)==1){REP(i,1,n+1) scanf("%d",&p[i]);memset(d,-1,sizeof(d));printf("%d\n", DP(1,n));}return 0;
}