aoj

ALDS1_10_B Matrix Chain Multiplication

ALDS1_10_B Matrix Chain Multiplication
Feb. 2, 2020, 1:52 p.m.

目次

解答

Naive recursive solution.

 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
#define INTMAX (1 << 21)

#define MAX 100


Int mcm(Int p[], Int left, Int right) {

    if (left == right) return 0;

    Int min_ = INTMAX;
    loop(sep,left,right) {
        Int cost = mcm(p, left, sep) + mcm(p, sep+1, right);
        cost += p[left - 1] * p[sep] * p[right];
        if (cost < min_) min_ = cost;
    }

    return min_;
}


int main(void) {
    Int n;
    cin >> n;
    Int p_len = n + 1;
    Int p[p_len];
    cin >> p[0] >> p[1];
    loop(i, 2, p_len) {
        cin >> p[i] >> p[i];
    }
    cout << mcm(p, 1, n) << endl;
    return 0;
}

解答

Bottom up dynamic programming. O(n^3)

 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
#define INTMAX (1 << 21)

#define MAX 100


Int mcm(Int p[], Int n) {
    Int mincosts[n][n];
    loop(i,1,n) mincosts[i][i] = 0;

    loop(chain,2,n) {
        loop(l,1,n-chain+1) {
            Int r = l + chain - 1;
            mincosts[l][r] = INTMAX;
            loop(k,l,r) {
                Int cost = mincosts[l][k] + mincosts[k+1][r];
                cost += p[l-1] * p[k] * p[r];
                if (cost < mincosts[l][r]) mincosts[l][r] = cost;
            }
        }
    }

    return mincosts[1][n-1];
}


int main(void) {
    Int n;
    cin >> n;
    Int p_len = n + 1;
    Int p[p_len];
    cin >> p[0] >> p[1];
    loop(i, 2, p_len) {
        cin >> p[i] >> p[i];
    }
    cout << mcm(p, p_len) << endl;
    return 0;
}