1. Erste Version: C, Rekursiv,  Evgeni Pavlidis


/**
* ACM programming Contest WS 08/09
* UVa Status: accepted
* Run Time: 0.590
* @author Evgeni Pavlidis evgenipavlidis@yahoo.de
*/
#include <iostream>
#include <cstdio>
#include <climits>
#include <string>

using namespace std;

int m[10][2];
int c[10][10];
int cut[10][10];
int caseNumber = 1;
char buf[3];

string printCut(int start, int end);
int minMult(int start, int end);

int main()
{
int matrices;

while(1)
{
scanf("%d",&matrices);
if(matrices == 0)
return 0;

int i;
for(i=0; i < matrices; i++)
scanf("%d %d\n", &m[i][0], &m[i][1]);

for(i=0; i < matrices; i++)
for(int j=0; j < matrices; j++)
c[i][j] = INT_MAX;

minMult(0,matrices-1);
cout << "Case " << caseNumber++ << ": " << printCut(0,matrices-1) << endl;
}
}

string printCut(int start, int end)
{
if(start == end)
{
sprintf(buf, "%d", start+1);
string number(buf);
return "A" + number;
}
else
return "(" + printCut(start, cut[start][end]) +
" x " + printCut(cut[start][end]+1, end) + ")";
}

int minMult(int start, int end)
{
if(start == end)
return 0;

if(c[start][end] != INT_MAX)
return c[start][end];

int k,current;
int min = INT_MAX;
for(k = start; k < end; k++)
{
current = minMult(start,k) + minMult(k+1,end)
+ m[start][0] * m[k][1] * m[end][1];

if(current < min)
{
min = current;
cut[start][end] = k;
}
}

return c[start][end] = min;
}



2. Zweite Version: C, Iterativ, Evgeni Pavlidis

/**
* ACM programming Contest WS 08/09
* UVa Status: accepted
* Run Time: 0.590
* @author Evgeni Pavlidis evgenipavlidis@yahoo.de
*/
#include <iostream>
#include <cstdio>
#include <climits>
#include <string>

using namespace std;

int m[10][2];
int c[10][10];
int cut[10][10];
int caseNumber = 1;
char buf[3];

string printCut(int start, int end);
int minMult(int start, int end);

int main()
{
int matrices;

while(1)
{
scanf("%d",&matrices);
if(matrices == 0)
return 0;

int i;
for(i=0; i < matrices; i++)
scanf("%d %d\n", &m[i][0], &m[i][1]);

minMult(0,matrices-1);
cout << "Case " << caseNumber++ << ": " << printCut(0,matrices-1) << endl;
}
}

string printCut(int start, int end)
{
if(start == end)
{
sprintf(buf, "%d", start+1);
string number(buf);
return "A" + number;
}
else
return "(" + printCut(start, cut[start][end]) +
" x " + printCut(cut[start][end]+1, end) + ")";
}

int minMult(int start, int end)
{
int current;
int matrices = end+1;

for(int t = 0; t < matrices; t++)
c[t][t] = 0;

for(int l = 1; l < matrices; l++)
for(int i = 0; i < matrices - l; i++)
{
int j = i+l;
c[i][j] = INT_MAX;
for(int k = i; k < j; k++)
{
current = c[i][k] + c[k+1][j]
+ m[i][0] * m[k][1] * m[j][1];

if(current < c[i][j])
{
//cout << i << j << " K = " << k << endl;
c[i][j] = current;
cut[i][j] = k;
}
}
}


return c[start][end];
}