開心的mdd

時間限制：1000?ms ?|? 內存限制：65535?KB 難度：3 描述

himdd有一天閑著無聊，隨手拿了一本書，隨手翻到一頁，上面描述了一個神奇的問題，貌似是一個和矩陣有關的東西。

給出三個矩陣和其行列A1（10*100），A2（100*5），A3（5*50）。現在himdd要算出計算矩陣所要的乘法次數，他發現不同的計算次序，所要的乘法次數也不一樣，

如：

(A1*A2)*A3 : 10*100*5+5*10*50=7500;

A1*(A2*A3) : 5*100*50+10*100*50 =75000;

他想知道計算矩陣所要的最少乘法次數是多少，很快一個解法就誕生了，有點小happy~~現在他想問問你是否也能找出一個解法呢？

注意：矩陣不可改變順序。

輸入

有多組測試數據（<=100)，每組表述如下：
第一行，有一個整數n矩陣的個數（1<=n<=100)
接下來有n行
第i行有兩整數，r,c表示第i個矩陣的行列;(1<=r,c<=100)

輸出

輸出計算矩陣所要的最少乘法次數。

樣例輸入

3 10 100 100 5 5 50

樣例輸出

7500

AC碼：

#include<stdio.h> #include<string.h> int min(int x,int y) {return x==0?y:(x<y?x:y); } int main() {int n,i,k,len;int m[105],dp[105][105];while(~scanf("%d",&n)){for(i=1;i<=n;i++){scanf("%d%d",&m[i-1],&m[i]);}memset(dp,0,sizeof(dp));for(len=1;len<n;len++) // len+1即為連乘的矩陣長度{for(i=1;i<=n-len;i++) // 連續相乘的矩陣的起點{int j=i+len; // 連續相乘的矩陣的終點for(k=i;k<j;k++) // k為斷點，如dp1..4,可以分為1~2 2~4和1~3 3~4dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+m[i-1]*m[k]*m[j]);}}printf("%d\n",dp[1][n]);}return 0; }

總結

以上是生活随笔為你收集整理的NYOJ 536 开心的mdd的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。