本文共 597 字，大约阅读时间需要 1 分钟。

1、

2、题目大意：

给出n个数，现在要将这些数一个一个的取出来，但是不能取出两个端点的数字，取出第i个数字（c[i]）的代价是

c[i-1]*c[i]*c[i+1]

用矩阵相乘的思想dp[i][j]表示i到j区间取出来的代价

dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+c[i]*c[k]*c[j])

3、AC代码：

#include
   
    #include
    
     using namespace std;#define N 105#define INF 0x7ffffffint c[N];int dp[N][N];int main(){    int n,tmp;    while(scanf("%d",&n)!=EOF)    {        for(int i=1;i<=n;i++)        scanf("%d",&c[i]);        for(int i=1;i<=n;i++)        dp[i][i]=0;        for(int i=2;i<=n;i++)        {            for(int j=1;j+i<=n;j++)            {                dp[j][j+i]=INF;                for(int k=j;k
    
   

转载地址：http://ugddi.baihongyu.com/