http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1276
裸的矩阵连乘问题。
1 #include<iostream> 2 #include<algorithm> 3 #include<string> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 8 int n; 9 int p[11]; 10 int m[11][11], s[11][11]; 11 12 void dp() 13 { 14 for (int i = 1; i <= n; i++) m[i][i] = 0; 15 for (int r = 2; r <= n;r++) 16 for (int i = 1; i <= n - r + 1; i++) 17 { 18 int j = i + r - 1; 19 m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j]; 20 s[i][j] = i; 21 for (int k = i + 1; k < j; k++) 22 { 23 int t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]; 24 if (t < m[i][j]) 25 { 26 m[i][j] = t; 27 s[i][j] = k; 28 } 29 } 30 } 31 } 32 33 34 void print(int i,int j) 35 { 36 if (i == j) 37 cout << "A" << i; 38 else 39 { 40 cout << "("; 41 print(i, s[i][j]); 42 cout << " x "; 43 print(s[i][j] + 1, j); 44 cout << ")"; 45 } 46 } 47 48 int main() 49 { 50 //freopen("D:\txt.txt", "r", stdin); 51 int kase = 0; 52 while (cin >> n&& n) 53 { 54 for (int i = 1; i <= n; i++) 55 cin >> p[i - 1] >> p[i]; 56 dp(); 57 cout << "Case " << ++kase << ": "; 58 print(1,n); 59 cout << endl; 60 } 61 return 0; 62 }