louisfghbvc的部落格

題目說明 :

在電腦科學領域中，影像處理是很受到許多人重視的一門學問，而影像處理常常需要做許多個矩陣相乘的計算，所以提升矩陣相乘的效率是很重要的。而多個矩陣相乘的效率可以取決於兩兩矩陣相乘的順序，順序不一樣，所需要做的總乘法量也不一樣，找出乘法量最小的就是效率最好的。例如有三個矩陣 M1 、 M2 、 M3M1 大小是 10X100 ， M2 大小是 100X5 ， M3 大小是 5X50 。現在要作這三個矩陣的連乘，假如是 ((M1M2)M3) ，那所需作的乘法量為10*100*5+10*5*50=7500 ，如果換成 (M1(M2M3)) ，則需要 100*5*50+10*100*50=75000 。由結果可之前者的方式效率較好。現在請你寫一個程式來決定多個矩陣連乘時，用括號來分乘法的順序，所需最小乘法量的方式。

輸入說明 :

輸入為多列資料，第一列內容為一正整數，代表矩陣個數。之後有幾列取決於矩陣有幾個，每一列有兩個正整數，代表矩陣大小。以上輸入的數範圍皆在 1 到 100000 之間。

輸出說明 :

輸出有兩列，第一列為像 ((M1(M2M3))(M4M5)) 這樣的格式，代表作矩陣連乘最有效率的方式。第二列為一正整數，代表所需要做的乘法量。

範例 :

思路:

row  col

DP為第i個矩陣乘到第j個矩陣 最小值 ,

假設矩陣 A1~A4, dp[i, j] = min(dp[i][j], dp[i][k] +  dp[k + 1][j] + row[i] * col[k](or row[k + 1]) * col[j]), k介於i, j 之間

就是以k為斷點, i乘到k之最小, 加上k+1乘到j之最小, 加上合併的和

至於為何是 + row[i] * col[k]* col[j] 因為dp[i][k] 矩陣最後不就是 row[i] * col[k]嗎

同樣道理 也可寫成 + row[i] * row[k + 1]* col[j], dp[k+1][j]矩陣 最後是 row[k+1] * col[j]

題外話: 我還是太菜了, 印出來的時候想不出來印法, 其實把這個當樹來弄就可以。

代碼:

#include <iostream>
#include <cstring>
#define N 1005
using namespace std;
int dp[N][N];
int p[N][N];
void print(int i, int j){
    if(i == j)
        cout << "M" << i + 1;
    else{
        int mid = p[i][j];
        cout << '(';
        print(i, mid);
        print(mid + 1, j);
        cout << ')';
    }
}
int main()
{
    int n;
    while(cin >> n){
        int arr[n][2];
        memset(dp, 0x7f, sizeof dp);
        memset(p, 0, sizeof p);

        for(int i = 0; i < n; ++i){
            cin >> arr[i][0] >> arr[i][1];
            dp[i][i] = 0;
        }
        for(int l = 1; l < n; ++l){
            for(int i = 0; i + l < n; ++i){
                int j = i + l;
                for(int k = i; k < j; ++k){
                    if(dp[i][j] > dp[i][k] + dp[k + 1][j] + arr[i][0] * arr[k][1] * arr[j][1]){
                        p[i][j] = k;
                        dp[i][j] = dp[i][k] + dp[k + 1][j] + arr[i][0] * arr[k][1] * arr[j][1];
                    }
                }
            }
        }
        print(0, n - 1);
        cout << endl << dp[0][n - 1] << endl;
    }
    return 0;
}