问题描述

对维数为序列<5,10,3,12,5,50,6>的各矩阵，找出其矩阵链乘积的一个最优加全部括号。

m矩阵

1
2
3
4
5
6
7
    [1]  [2]  [3]  [4]  [5]  [6]
[1]   0  150  330  405 1655 2010
[2]   0    0  360  330 2430 1950
[3]   0    0    0  180  930 1770
[4]   0    0    0    0 3000 1860
[5]   0    0    0    0    0 1500
[6]   0    0    0    0    0    0

s矩阵

1
2
3
4
5
6
7
    [1]  [2]  [3]  [4]  [5]  [6]
[1]   0    1    2    2    4    2
[2]   0    0    2    2    2    2
[3]   0    0    0    3    4    4
[4]   0    0    0    0    4    4
[5]   0    0    0    0    0    5
[6]   0    0    0    0    0    0

代码部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

#define N 1010

int n;
int p[N], m[N][N], s[N][N];

// p用来记录矩阵，m[i][j]表示第i个矩阵到第j个矩阵的最优解，s[][]记录从哪里断开可以得到最优解
void matrixChain() {
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            m[i][j] = 0;
    for (int l = 2; l <= n; l++) {              //对角线循环
        for (int i = 1; i <= n - l + 1; i++) {  //行循环
            int j = i + l - 1;                  //列的控制
            m[i][j] = m[i + 1][j] +
                      p[i - 1] * p[i] * p[j];  //找m[i][j]的最小值，初始化使k=i;
            s[i][j] = i;
            for (int k = i + 1; k < j; k++) {
                int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (t < m[i][j]) {
                    s[i][j] = k;  //在k位置断开得到最优解
                    m[i][j] = t;
                }
            }
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i <= n; i++)
        cin >> p[i];
    matrixChain();
    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= n; j++)
    //         cout << m[i][j] << " ";
    //     cout << endl;
    // }
    // cout << endl;
    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= n; j++)
    //         cout << s[i][j] << " ";
    //     cout << endl;
    // }
    return 0;
}