c112. Optimal Array Multiplication Sequence
http://zerojudge.tw/ShowProblem?problemid=c112
內容 ：
給你2個矩陣A、B，我們使用標準的矩陣相乘定義C=AB如下：
A 陣列中欄（column）的數目一定要等於B陣列中列（row）的數目才可以做此2陣列的相乘。若我們以rows(A)，columns(A)分 別代表A陣列中列及欄的數目，要計算C陣列共需要的乘法的數目為：rows(A)*columns(B)*columns(A)。例如：A陣列是一個 10x20的矩陣，B陣列是個20x15的矩陣，那麼要算出C陣列需要做10*15*20，也就是3000次乘法。
要計算超過2個以上的矩陣相乘就得決定要用怎樣的順序來做。例如：X、Y、Z都是矩陣，要計算XYZ的話可以有2種選擇：(XY)Z 或者 X(YZ)。假設X是5x10的陣列，Y是10x20的陣列，Z是20x35的陣列，那個不同的運算順序所需的乘法數會有不同：
(XY)Z
- 5*20*10 = 1000次乘法完成(XY)，並得到一5x20的陣列。
- 5*35*20 = 3500次乘法得到最後的結果。
- 總共需要的乘法的次數：1000+3500=4500。
X(YZ)
- 10*35*20 = 7000次乘法完成(YZ)，並得到一10x35的陣列。
- 5*35*10 = 1750次乘法得到最後的結果。
- 總共需要的乘法的次數：7000+1750=8750。
很明顯的，我們可以知道計算(XY)Z會使用較少次的乘法。
這個問題是：給你一些矩陣，你要寫一個程式來決定該如何相乘的順序，使得用到乘法的次數會最少。
輸入說明
：
含有多組測試資料，每組測試資料的第一列，含有1個整數N（N <= 10）代表有多少個陣列要相乘。接下來有N對整數，代表一陣列的列數及欄數。這N個陣列的順序與要你相乘的陣列順序是一樣的。
N=0代表輸入結束。請參考Sample Input。
輸出說明
：
每組測試資料輸出一列，內容為矩陣相乘的順序（以刮號來表示）使得所用的乘法次數最小。如果有不只一組答案，輸出任一組均可。請參考Sample Output。
範例輸入 ：
3 1 5 5 20 20 1 3 5 10 10 20 20 35 6 30 35 35 15 15 5 5 10 10 20 20 25 0
範例輸出 ：
Case 1: (A1 x (A2 x A3)) Case 2: ((A1 x A2) x A3) Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))
提示
：
* Luck 貓翻譯
出處
：
作法 : DP & 回朔
DP 紀錄最小值的走法，然後進行回朔
/**********************************************************************************/
/* Problem: c112 "Optimal Array Multiplication Sequence" from ACM 348 */
/* Language: C */
/* Result: AC (0ms, 278KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-13 22:07:56 */
/**********************************************************************************/
#include<stdio.h>
int DP[11][11] = {}, a, b, c, d;
int Wy[11][11] = {};
void Backtracking(int l, int r) {
if(l+1 < r) {
int m = Wy[l][r];
printf("(");
Backtracking(l, m);
printf(" x ");
Backtracking(m+1, r);
printf(")");
}
if(l == r)
printf("A%d", l+1);
if(l+1 == r)
printf("(A%d x A%d)", l+1, r+1);
}
main() {
int n, A[11], C = 0;
while(scanf("%d", &n) == 1 && n) {
for(a = 0; a < n; a++)
scanf("%d %d", &A[a], &A[a+1]);
for(a = 1; a < n; a++) {
for(b= 0, c= a + b; c < n; b++, c++) {
int min = 2147483647, t, set;
for(d = b; d < c; d++) {
t = DP[b][d] + DP[d+1][c] + A[b]*A[d+1]*A[c+1];
if(min > t) {
min = t, set = d;
}
}
DP[b][c] = min, Wy[b][c] = set;
}
}
printf("Case %d: ", ++C);
Backtracking(0, n-1);
puts("");
}
return 0;
}
上一篇：c109. Cipher
下一篇：c125. Frogger