1. C++, Axel Fiedler


/*
* ACM Programming Contest
*
* Problem: 348 - Optimal Array Multiplication Sequence
* Status: Accepted
* Language: C
* Runtime: 0.056
* Date: 2009-06-07 19:30:15
* Author: Axel Fiedler
*
*/
#include <stdio.h>
#include <string.h>
#include <limits.h>

#define MAX_SIZE 100
#define MAX_ARRAYS 10

int m[MAX_SIZE][MAX_SIZE];
int queue[MAX_SIZE][MAX_SIZE];
int row[MAX_ARRAYS];
int col[MAX_ARRAYS];

void print(int i, int j)
{
if (i == j)
printf("A%d", i + 1);
else
{
printf("(");
print(i, queue[i][j]);
printf(" x ");
print(queue[i][j] + 1, j);
printf(")");
}
}

int main()
{
int i, j, k, l, n, max, counter = 1;

while (scanf("%d", &n) && (n > 0))
{
for (i = 0; i < n; i++)
scanf("%d %d", &row[i], &col[i]);

for (l = 1; l < n; l++)
{
for (i = 0; i < n - l; i++)
{
j = i + l;
m[i][j] = INT_MAX;

for (k = i; k < j; k++)
{
max = m[i][k] + m[k + 1][j] + row[i]*col[k]*col[j];

if (max < m[i][j])
{
m[i][j] = max;
queue[i][j] = k;
}
}
}
}

printf("Case %d: ", counter);
print(0, n - 1);
printf("\n");

counter++;
}

return 0;
}