uvaoj 348 - Optimal Array Multiplication Sequence 构造答案

uvaoj 348 - Optimal Array Multiplication Sequence 给定n个矩阵的序列，求出使得矩阵乘法的运算量最小的运算方法，输出格式见样例。在枚举i到j的位置k的时候，记录最优的这个k就可以了，所以要用另外一个数组来存储这个k。得出来后，递归的构造答案就行了，当只有一个矩阵的时候输出，否则就从k位置断开，递归构造。递归写起来方便。这个数组记录的是绝对的位置k。可以在构造的时候直接打印答案，不用保存。做这道题目的时候遇到了十分奇葩的问题，最神奇的是还不知道是什么原因。 代码如下：

/*************************************************************************
	> File Name: 348.cpp
	> Author: gwq
	> Mail: [email protected] 
	> Created Time: 2014年11月16日 星期日 12时12分27秒
 ************************************************************************/

#include <cmath>
#include <ctime>
#include <cctype>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>

#define INF (INT_MAX / 10)
#define clr(arr, val) memset(arr, val, sizeof(arr))
#define pb push_back
#define sz(a) ((int)(a).size())

using namespace std;
typedef set<int> si;
typedef vector<int> vi;
typedef map<int, int> mii;
typedef long long ll;

const double esp = 1e-5;

#define N 15

//pre[i][j]记录第i个矩阵到第j个矩阵相乘最优的绝对位置
int w[N], dp[N][N], pre[N][N], n;

//先短区间，后长区间
void solve(void)
{
	for (int i = 0; i < n; ++i) {
		for (int j = 1; j + i <= n; ++j) {
			dp[j][j + i] = (i == 0) ? 0 : INF;
			//dp[j][j + i] = (i == 0) ? 0 : INT_MAX;
			//刚开始在这里，pre不初始化或者初始化为j，就AC，初始化
			//为其他的就RE，不知道是什么原因。pre[i][j+i]当i为0时，
			//在后边构造答案的时候就没有用到，其他的一定会被覆盖，
			//所以说，初始化为任何值都是可以的，但是不知道什么原因。
			//后来想到INF可能不够大，就换成了INT_MAX，竟然AC了，
			//可是如果INF不够大的话，怎么会在使用INF的时候，并且
			//不初始化的时候AC呢？我真是搞不懂了。
			//pre[j][j + i] = j;
			//pre[j][j + i] = (i == 0) ? 0 : j;
			//pre[j][j + i] = 0;
			for (int k = j; k < j + i; ++k) {
				int tmp = dp[j][k] + dp[k + 1][j + i]
					+ w[j - 1] * w[k] * w[j + i];
				if (dp[j][j + i] > tmp) {
					dp[j][j + i] = tmp;
					pre[j][j + i] = k;
				}
			}
		}
	}
}

//构造最优解，当只有一个矩阵时，应该直接打印
void getans(int l, int r)
{
	if (l > r) {
		return;
	} else if (l == r) {
		printf("A%d", l);
	} else {
		int k = pre[l][r];
		printf("(");
		getans(l, k);
		printf(" x ");
		getans(k + 1, r);
		printf(")");
	}
}

int main(int argc, char *argv[])
{
	int c = 0;
	while (scanf("%d", &n) != EOF) {
		if (n == 0) {
			break;
		}
		for (int i = 1; i <= n; ++i) {
			scanf("%d%d", &w[i - 1], &w[i]);
		}
		printf("Case %d: ", ++c);
		solve();
		getans(1, n);
		printf("\n");
	}

	return 0;
}