经典DP，矩阵链乘，不过此题不要求算最小的相乘次数，而要把最优的解输出，那一个数组记录从i到j的最优分割，然后递归输出就行了。
而关于具体的转移方程资料到处都有。就不做说明了，具体参见代码。
代码是O(n^3)此方的解法，据说斯坦福大学的一片论文有O(nlogn)的，改天研究下。。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 15
struct Array
{
int row, col;
}array[N];
int a[N][N], p[N][N];
void show(int left, int right)
{
if(left < right)
{
printf("(");
show(left, p[left][right]);
printf(" x ");
show(p[left][right] + 1, right);
printf(")");
}
else if(left == right)
{
printf("A%d", left);
}
}
int main()
{
int n, cas = 0;
while(scanf("%d", &n), n)
{
for(int i = 1; i <= n; i++)
scanf("%d %d", &array[i].row, &array[i].col);
memset(a, 127, sizeof(a));
memset(p, 0, sizeof(p));
for(int i = 1; i <= n; i++) a[i][i] = 0;
for(int i = 2; i <= n; i++)
{
a[i - 1][i] = array[i - 1].row * array[i].row * array[i].col;
p[i - 1][i] = i - 1;
}
for(int i = 3; i <= n; i++)
for(int j = i - 2; j; j--)
for(int k = j; k < i; k++)
{
int t = a[j][k] + a[k + 1][i] + array[j].row * array[k].col * array[i].col;
if(a[j][i] > t)
{
a[j][i] = t;
p[j][i] = k;
}
}
printf("Case %d: ", ++cas);
show(1, n);
printf("\n");
}
return 0;
}