[UVA] 348 - Optimal Array Multiplication Sequence

題目鏈接

題意：

給你n個矩陣，求矩陣相乘的順序，
使得運算量最小。
矩陣A為a*b
矩陣B為b*c

矩陣相乘運算量為
a*b*c

我的作法：

dynamic programming
dp[ i ][ j ]為第 i 個矩陣到第 j 個矩陣的最小運算量
dp[ i ][ i ] = 0

其基本想法是這樣：
若有一 k 在 i 和 j 中間，
就可以將運算分成
第 i 個矩陣相乘到第 k 個矩陣，形成矩陣A，
再將矩陣A一路乘到矩陣 j ，
找到 k 可以使得 i 到 j 運算量最小 。

假設
第 i 個矩陣為a*b

第 k 個矩陣為c*d

第 j 個矩陣為e*f

dp[ i ][ j ] = dp[ i ][ k ] + dp[ k+1 ][ j ] + a*d*f ;
枚舉 k 從 i 到 j，找到最小值就是dp[ i ][ j ]值，
而形成最小值的 k 就是切割點，
cut[ i ][ j ] = k
就是表示第 i 個矩陣乘到第 j 個矩陣要先做 i 到 k 再做 k 到 j 的相乘。
最後輸出依據切割點遞迴輸出。

--------------------------------------------------

/* 20151128
 * hanting
 * UVa 348 - Optimal Array Multiplication Sequence
 * C++
 */
#include <iostream>
#include <cstring>
using namespace std;
pair<int, int> matrix[12];
int dp[12][12];
int cut[12][12];
int MCM(int i, int j)
{
    if(dp[i][j] != -1) return dp[i][j];
    if(i == j)
    {
        return dp[i][j] = 0;
    }
    else
    {
        int mini = 0x3fffffff;
        for(int k = i; k < j; k++)
        {
            int tmp = MCM(i, k) + MCM(k+1, j) + matrix[i].first * matrix[k].second * matrix[j].second;
            if(mini > tmp)
            {
                mini = tmp;
                cut[i][j] = k;
            }
        }
        return dp[i][j] = mini;
    }
}
int output(int i,int j)
{
    if(i == j)
    {
        cout << "A" << i+1;
    }
    else
    {
        cout << "(";
        output(i, cut[i][j]);
        cout << " x ";
        output(cut[i][j]+1, j);
        cout << ")";
    }
}
int main()
{
    int N;
    int testCase = 1;
    while(cin >> N and N)
    {
        for(int i = 0; i < N; i++)
        {
            cin >> matrix[i].first >> matrix[i].second;
        }
        memset(dp, -1, sizeof(dp));
        MCM(0, N-1);
        cout << "Case " << testCase++ << ": " ;
        output(0, N-1);
        cout << endl;
    }
    return 0;
}