UVa 348 Optimal Array Multiplication Sequence:区间DP&矩阵链乘,MCM

UVa 348 Optimal Array Multiplication Sequence:区间DP&矩阵链乘,MCM2014-07-27 csdn博客 synapse7

348 - Optimal Array Multiplication Sequence

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=284

记忆化搜索：dp[a][b] = max（dp[a][b], dp[a][i] + dp[i + 1][b] + x[a] * y[i] * y[b]）

完整代码：

/*0.089s*/#include <cstdio>#include <cstring>const int MAXN = 15;int x[MAXN], y[MAXN], d[MAXN][MAXN], path[MAXN][MAXN];int dp（int a, int b）{if （d[a][b] >= 0） return d[a][b];path[a][b] = a;if （a == b） return d[a][b] = 0;d[a][b] = -1u >> 1;int tmp;for （int i = a; i < b; ++i）{tmp = dp（a, i） + dp（i + 1, b） + x[a] * y[i] * y[b];if （tmp < d[a][b]）d[a][b] = tmp, path[a][b] = i;}return d[a][b];}void print（int a, int b）{if （a > b） return;if （a == b） printf（"A%d", a + 1）;else{printf（"（"）;print（a, path[a][b]）;printf（" x "）;print（path[a][b] + 1, b）;printf（"）"）;}}int main（）{int n, cas = 0;while （scanf（"%d", &n）, n）{memset（d, -1, sizeof（d））;for （int i = 0; i < n; i++）scanf（"%d%d", &x[i], &y[i]）;dp（0, n - 1）;printf（"Case %d: ", ++cas）;print（0, n - 1）;putchar（10）;}return 0;}