本文主要是介绍UVa 348 Optimal Array Multiplication Sequence (区间DP矩阵链乘,MCM)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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;
}
这篇关于UVa 348 Optimal Array Multiplication Sequence (区间DP矩阵链乘,MCM)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
