alan23273850 的刷題筆記
c112: 00348 - Optimal Array Multiplication Sequence
Tags: dp
出處：https://zerojudge.tw/ShowProblem?problemid=c112
提交：https://zerojudge.tw/Submissions?problemid=c112&account=allllllan123456
問題：給定連續 $N\in[1,10]$ 個矩陣各自的列數與欄數，前一個矩陣的欄數必定等於後一個矩陣的列數，請問該用什麼樣的順序進行矩陣乘法才能使得全部使用的乘法次數會最少？
解法：這題是聖經本 Introduction to Algorithms 第三版裡面第 15.2 的經典章節。對於一個矩陣串 A[1:n]，我們想從 1 ~ n 之中挑一個最好的切割點 j，使得先對 A[1:j] 作相乘結合的成本 X，再對 A[j+1:n] 作相乘結合的成本 Y，與最後對這兩個結果 A[1:j]、A[j+1:n] 作相乘結合的成本 Z 之總和 X + Y + Z 要最小。因為每個子問題都會被檢查到，所以這題其實可以使用 bottom up 的 DP。另外本題敘述有個小瑕疵就是它其實並沒有啟用 special judge，當我們遇到多組解的時候，要盡量把矩陣塞到左括號內，也就是讓左括號內的矩陣數量愈多愈好，這樣才會 AC。
1#include <bits/stdc++.h>
2using namespace std;
3
4int separator[11][11];
5
6string print(int x, int y) { assert(x <= y);
7 if (x == y) return "A" + to_string(x);
8 return "(" + print(x, separator[x][y]) + " x " + print(separator[x][y]+1, y) + ")";
9}
10
11int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
12 int cost[11][11], size[11], n, cases=0;
13 for (int i=1; i<=10; i++) cost[i][i] = 0;
14 while (cin>>n && n) {
15 for (int i=0; i<n; i++) // input size[0:n]
16 cin >> size[i] >> size[i+1];
17 for (int d=1; d<n; d++)
18 for (int i=1; i+d<=n; i++) {
19 cost[i][i+d] = INT_MAX;
20 for (int j=i; j<i+d; j++) {
21 int temp = cost[i][j] + cost[j+1][i+d] + size[i-1]*size[j]*size[i+d];
22 if (temp <= cost[i][i+d]) { /* since this problem has no special judge... */
23 cost[i][i+d] = temp;
24 separator[i][i+d] = j;
25 }
26 }
27 }
28 cout << "Case " << (++cases) << ": " << print(1, n) << '\n';
29 }
30 return 0;
31}