線性代數中的矩陣問題

Time Limit: 1000 MS Memory Limit: 32768 K Total Submit: 64(34 users) Total Accepted: 32(27 users) Rating:  Special Judge: No

Description

一個n*m矩陣由n行m列共n*m個數排列而成。兩個矩陣A和B可以相乘當且僅當A的列數等于B的行數。 一個n*m的矩陣乘以一個m*p的矩陣可以轉化成一個n*p的矩陣，運算次數為n*m*p。 矩陣乘法滿足結合律，A*B*C可以表示成(A*B)*C或者是A*(B*C)，兩者的運算次數卻不同。 例如當A=2*3 B=3*4 C=4*5時，(A*B)*C=(2*3*4)+(2*4*5)=64而A*(B*C)=(2*3*5)+(3*4*5)=90。 顯然第一種順序節省運算次數。 給出n個矩陣組成的序列，設計一種方法把他們依次乘起來，使得總的運算次數盡量小。

Input

輸入第一行為數據組數T(T<=20)。 對于每組測試數據 第一行是一個整數n(n<=100)代表有多少個矩陣。 第二行是n+1個整數，依次相鄰的倆個數表示相鄰矩陣的行列數。如Hint所示。 每個矩陣的行數和列數均不大于20

Output

對于每組測試數據輸出最優的計算次數。

Sample Input

1 3 2 3 4 5

Sample Output

64

Hint

如第一組測試數據3個矩陣依次為2*3和3*4和4*5。

Author

陳禹@HRBUST

思路：

1、問題可以看成：一共有N+1個數，每一次拿取a【i】，獲得a【i】*a【i-1】*a【i+1】的價值。兩邊元素一直保留不變。

2、那么問題同Poj 1651，有興趣的小伙伴可以去做一下，題目是基本一樣的；

設定dp【i】【j】表示已經拿完了區間：【i，j-1】的所有數之后的最小總價值。

3、那么其狀態轉移方程的重點放在區間合并上來：

dp【i】【j】=min（dp【i】【j】，dp【i】【k】+dp【k+1】【j】+a【k】*a【j】*a【i-1】）；

#include<stdio.h>#include<iostream>#include<string.h>using namespace std;int dp[125][125];int a[125];int main(){    int t;    scanf("%d",&t);    while(t--)    {        int n;        scanf("%d",&n);        n++;        for(int i=0; i<n; i++)        {            scanf("%d",&a[i]);        }        for(int len=1; len<n; len++)        {            for(int i=1; i<n-1; i++)            {                int j=i+len;                dp[i][j]=0x3f3f3f3f;                for(int k=i; k<j; k++)                {                    dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+a[k]*a[i-1]*a[j]);                }            }        }        PRintf("%d/n",dp[1][n-1]);    }}