1.

/**
* ACM Training 2009
* ACM Problem #348 - Optimal Array Multiplication Sequence
* Link: http://uva.onlinejudge.org/external/3/348.pdf
*
* @author Felix Dietrich
* @version 1.0, 09/17/2009
*
* Methode: DP
* Status : Accepted
* Runtime: 2.060
*/

import java.util.Scanner;


public class Main
{
static int matrixNumber;
static int[][] multiplications;
static int[] openBrackets;
static int[] closedBrackets;

public static void main(String... strings)
{
Scanner sc = new Scanner(System.in);
int caseNumber = 1;
int[] matrices;

while(sc.hasNext())
{
/////////////
// READ Info

matrixNumber = sc.nextInt();
if(matrixNumber == 0)
return;

matrices = new int[matrixNumber*2];
openBrackets = new int[matrixNumber];
closedBrackets = new int[matrixNumber];
multiplications = new int[matrixNumber][matrixNumber];
for(int i=0; i<matrixNumber; i++)
{
matrices[i*2] = sc.nextInt();
matrices[i*2+1] = sc.nextInt();

for(int k=i+1;k<matrixNumber; k++)
multiplications[i][k] = -1;
multiplications[i][i] = 0;
}

////////////////////
// START DP
calculate(matrices, 0, matrixNumber);

// PRINT Solution
print(String.format("Case %d: %s", caseNumber++, printBrackets(0,matrixNumber)));
}
}

/**
* Prints the matrix chain in the precomputed order
* @param i left index
* @param j right index +1
* @return bracket expression
*/
private static String printBrackets(int i, int j)
{
String result;
if(i==j-1)
result = "A"+(i+1);
else if(i==j-2)
result = String.format("(A%d x A%d)", i+1,j);
else
{
int k=multiplications[j-1][i];
result = String.format("(%s x %s)", printBrackets(i, k+1), printBrackets(k+1, j));
}
return result;
}

/**
* Dynamic Programming function, calculates the optimal bracket order
* for the matrix multiplication
*
* @param matrices the row/colum count for each matrix
* @param i left index
* @param j right index +1
* @return minimum of multiplications needed
*/
private static int calculate(int[] matrices, int i, int j)
{
int minimalK = 0;
int minimalMults = Integer.MAX_VALUE;
int currentMults;

// only one matrix
if(i==j)
{
return 0;
}
// two matrices
if(i+2==j)
{
currentMults = matrices[i*2]*matrices[i*2+1]*matrices[j*2-1];
multiplications[i][j-1]=currentMults;
return currentMults;
}
// already computed
if(multiplications[i][j-1] != -1)
{
return multiplications[i][j-1];
}

// split up the matrix chain from i to j into two chains
// and compute the minimum.
// min { C[i][k+1] + C[k+1][j] + di*2 * dk*2+1 * dj*2-1 }
for(int k=i; k<j-1; k++)
{
currentMults = calculate(matrices, i, k+1)+calculate(matrices, k+1, j)+matrices[i*2]*matrices[k*2+1]*matrices[j*2-1];

if(minimalMults > currentMults)
{
minimalMults = currentMults;
minimalK = k;
}
}

multiplications[i][j-1]=minimalMults;
multiplications[j-1][i]=minimalK;

return minimalMults;
}

private static void print(String format)
{
System.out.println(format);
}
}

2.

/*
* 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;
}