UVA/arraymult.c at master · mjimaz/UVA · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <stdio.h>
#include <string.h>

#define MAX 15
#define INFINITY 2000000000

int s[MAX][MAX];
char optPar[100000];
int strIndex;

void print(int from, int to){
    if(from==to){
       optPar[strIndex] = 'A';
       strIndex++;
    }

    else{

      optPar[strIndex]='(';
      strIndex++;
      print(from,s[from][to]);
      optPar[strIndex] = ' ';
      strIndex++;
      optPar[strIndex] = 'x';
      strIndex++;
      optPar[strIndex] = ' ';
      strIndex++;
      print(s[from][to]+1,to);

      optPar[strIndex] = ')';
      strIndex++;
   }

}

int main(){
	int n, r;
	int i,j,k,L;
	int mult[MAX][MAX];
	int p[MAX];
	int q, m;
	int cases=1;

	while(1){
		scanf("%d",&n);

		if(n == 0)
			break;
		i=0;

		scanf("%d",&p[i]);
		r=0;

		while(1){
			if(i == n)
				break;
			if(r == 0){
				i++;
				scanf("%d",&p[i]);
				r=1;
			}else{
				scanf("%d",&j);
				r=0;
			}
		}
		for(i=1;i<=n;i++)
			mult[i][i] = 0;

		for(L=2;L<=n;L++)
			for(i=1;i<=n-L+1;i++){
				j = i + L -1;
				mult[i][j] = INFINITY;
				for(k = i;k<=j-1;k++){
					q = mult[i][k] + mult[k+1][j] + p[i-1]*p[k]*p[j];
					if (q < mult[i][j]) {
						mult[i][j] = q;
						s[i][j] = k;
					}
				}
		}
		strIndex = 0;
		print(1,n);
		j=1;
		n = strlen(optPar);

		printf("Case %d: ",cases++);
		for(i=0;i<n;i++){
			printf("%c",optPar[i]);
			if(optPar[i] == 'A')
				printf("%d",j++);
		}
		printf("\n");
	}
	return 0;
}