题意:
有N个矩阵相乘,不同的相乘顺序会有不同的次数,求一种顺序,使相乘的次数最小。
思路:
简单的区间DP,麻烦的是要把这个顺序打印出来,要用到递归,需要学习,第二次碰到。
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> long long int dp[15][15]; int a[15], path[15][15]; int n; void print(int i, int j) { if (i == j) printf("A%d", i + 1); else { printf("("); print(i, path[i][j]); printf(" x "); print(path[i][j] + 1, j); printf(")"); } } int main() { int cases = 0; while (scanf("%d", &n) && n) { for (int i = 0; i < n; ++i) scanf("%d %d", &a[i], &a[i+1]); memset(dp, 0, sizeof(dp)); memset(path, 0, sizeof(path)); for (int d = 1; d < n; ++d) { for (int i = 0, j = d; j < n; ++i, ++j) { dp[i][j] = LLONG_MAX; for (int k = i; k < j; ++k) { int t = dp[i][k] + dp[k+1][j] + a[i] * a[k+1] * a[j+1]; if (dp[i][j] > t) dp[i][j] = t, path[i][j] = k; } } } printf("Case %d: ", ++cases); print(0, n - 1); printf("\n"); } return 0; }