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; }