UVA - 348Optimal Array Multiplication Sequence（递推）

id=19208">题目：Optimal Array Multiplication Sequence

题目大意：给出N个矩阵相乘。求这些矩阵相乘乘法次数最少的顺序。

解题思路：矩阵相乘不满足交换率但满足结合率。dp【i】【j】 代表第1个矩阵到第j个矩阵之间的最少的乘法次数，转移状态方程：dp【i】【j】 = Min(dp【i】【k】 + dp【k + 1】【j】  + A[i - 1] * A[k] *A[j]) k>= i && k <= j - 1。A0A1A2A3..Ak  |  Ak+1AK+2Aj， 第i个矩阵的行Ai - 1 ，列Ai。上面那个式子的意思是在K这个地方断开。两边的矩阵都先做相乘，这样左右两边的相乘是互不影响的。这样左右两边的相乘也是採取找最优的形式（最优的子结构）。全部就有上面的状态转移方程。最后是路径输出，我没有记录路径而是直接用递归的写法，可是这里要注意仅仅要找一种最优序列就好了（有的矩阵相乘存在多种最优序列），在递归中少了一个break害我wa了好久，找不到原因。

代码：

#include <cstdio>

#include <cstring>

typedef long long ll;

const int INF = 0x7fffffff;

const int N = 15;

ll A[N];

int n;

ll dp[N][N];

ll Min (const ll a, const ll b) { return a < b?

a: b;}

void printf_ans (int s, int e) {

	if (s == e) {

		printf ("A%d", s);

		return;

	}

	for (int i = s; i < e; i++) {

		if ((dp[s][i] + dp[i + 1][e] + A[s - 1] * A[i] * A[e]) == dp[s][e]) {

			if (s != i)

				printf ("(");

			printf_ans(s, i);

			if (s != i)

				printf (")");

			printf (" x ");

			if (i + 1 != e)

				printf ("(");

			printf_ans(i + 1, e);

			if (i + 1 != e)

				printf (")");

			break;

		}

	}

}

int main () {

	int cas = 0;

	while (scanf ("%d", &n), n) {

		for (int i = 0; i < n; i++)

			scanf ("%lld%lld", &A[i], &A[i + 1]);

		for (int i = 1; i <= n; i++)

			dp[i][i] = 0;

		ll temp;

		for (int len = 1; len < n; len++)

			for (int i = 1; i + len <= n; i++) {

				temp = INF;

				for (int k = 0; k < len; k++)

					temp = Min (temp, dp[i][i + k] + dp[i + k + 1][i + len] + A[i - 1] * A[i + k] * A[i + len]);

				dp[i][i + len] = temp;

			}

//	    printf ("%lld\n", dp[1][n]);

		printf ("Case %d: (", ++cas);

		printf_ans(1, n);

		printf (")\n");

	}

	return 0;

}