時限：

1000ms 內(nèi)存限制：10000K? 總時限：3000ms

描述：

在科學(xué)計算中經(jīng)常要計算矩陣的乘積。矩陣A和B可乘的條件是矩陣A的列數(shù)等于矩陣B的行數(shù)。若A是一個p×q的矩陣，B是一個q×r的矩陣，則其乘積C=AB是一個p×r的矩陣。計算C=AB總共需要p×q×r次乘法。 現(xiàn)在的問題是，給定n個矩陣{A1,A2,…,An}。其中Ai與Ai+1是可乘的，i=1,2,…,n-1。 要求計算出這n個矩陣的連乘積A1A2…An最少需要多少次乘法。

輸入：

輸入數(shù)據(jù)的第一行是一個整數(shù)n（0 < n <= 10），表示矩陣的個數(shù)。 接下來的n行每行兩個整數(shù)p,q( 0 < p,q < 100)，分別表示一個矩陣的行數(shù)和列數(shù)。

輸出：

輸出一個整數(shù)：計算連乘積最少需要乘法的次數(shù)。

輸入樣例：

10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11

輸出樣例：

438

#include<stdio.h> int n;//矩陣個數(shù)(0~10) int p[11];//矩陣維數(shù)(n+1)void Matrix_mult() {int Arr[11][11],temp;//(a[0][0]不用)a[i][j]存放從矩陣i到矩陣j的最小矩陣乘法數(shù)int i,j,k;int d;//矩陣間隔dfor(i=1;i<=n;i++)Arr[i][i]=0;//第i個矩陣到第i個矩陣乘法數(shù)為1for(d=1;d<=n-1;d++)//矩陣間隔r//矩陣鏈長度d+1 {for(i=1;i<=n-d;i++)//i=1..~n-d{ j=i+d;//i~i+d構(gòu)成長度為r+1的矩陣鏈Arr[i][j]=0+Arr[i+1][j]+p[i-1]*p[i]*p[j];//截斷位置為ifor(k=i+1;k<j;k++)//截斷位置為k=i+1,i+2.....j-1 {temp=Arr[i][k]+Arr[k+1][j]+p[i-1]*p[k]*p[j];if(temp<Arr[i][j])Arr[i][j]=temp;//獲得從矩陣i到矩陣j的最小矩陣乘法數(shù) }}}printf("%d\n",Arr[1][n]);//從第1個矩陣到第n個矩陣最小乘法數(shù) } int main() {int i;scanf("%d",&n);//矩陣個數(shù)(0~10) int b[10][2];for( i=0;i<n;i++){ scanf("%d",&b[i][0]);//第i個矩陣的行數(shù)scanf("%d",&b[i][1]);//第i個矩陣的列數(shù) }for(i=0;i<n;i++)p[i]=b[i][0];//存放所有矩陣維數(shù)（測例中的1,2,3...10,11）p[n]=b[n-1][1];Matrix_mult();return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/IThaitian/archive/2012/07/11/2586788.html

總結(jié)

以上是生活随笔為你收集整理的计算矩阵连乘积(动态规划)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。