1249.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1249 on 2006-01-09 at 12:38:03 */ 
#include <cstdio>

const int MAX = 16;
const int INF = 2000000000;

int best[MAX][MAX], div[MAX][MAX];

void print(int, int);

int main()
{
	int n, r[MAX], c[MAX];
	int i, j, d, m, t;
	
	for(t = 1; scanf("%d", &n) != EOF && n != 0; t++) {
		for(i = 0; i < n; i++) scanf("%d %d", &r[i], &c[i]), best[i][i] = 0;
		for(d = 1; d < n; d++) {
			for(i = 0; (m = i+d) < n; i++) {
				best[i][m] = INF;
				for(j = i; j <= m; j++) {
					if(best[i][m] > best[i][j]+best[j+1][m]+r[i]*c[j]*c[m]) {
						best[i][m] = best[i][j]+best[j+1][m]+r[i]*c[j]*c[m];
						div[i][m] = j;
					}
				}
			}
		}
		printf("Case %d: (", t);
		print(0, n-1);
		printf(")\n");
	}
	
	return 0;
}

void print(int b, int e)
{
	if(div[b][e] == b) printf("A%d", b+1);
	else { putchar('('); print(b, div[b][e]); putchar(')'); }
	printf(" x ");
	if(div[b][e]+1 == e) printf("A%d", e+1);
	else { putchar('('); print(div[b][e]+1, e); putchar(')'); }
}