算法-2018-11-08-noj-1048-矩阵连乘

#include<stdio.h>
#include<string.h>

#define N 10
#define INF 0x7FFFFFFF

int main(void)
{
    int n;
    int row[N],col[N],re[N][N];
    int i,j,k,mini;
    while(scanf("%d",&n)!=EOF)
    {
        memset(re,0x0,sizeof(re));
        for(i=0;i<n;i++)
            scanf("%d%d",row+i,col+i);
        for(i=1;i<n;i++)
            re[i-1][i] = row[i-1]*row[i]*col[i];
        for(i=2;i<n;i++)
        {
            for(j=0;i+j<n;j++)
            {
                for(k=0,mini=INF;k<i;k++)
                {
                    if( mini > re[j][j+k] + re[j+k+1][j+i] + row[j]*col[j+k]*col[j+i] )
                        mini = re[j][j+k] + re[j+k+1][j+i] + row[j]*col[j+k]*col[j+i] ;
                }
                re[j][j+i] = mini;
            }
        }
        printf("%d\n",re[0][n-1]);
    }
    return 0;
}

也算是一个不错的题目。