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
|
#define N 11
int path[N][N];
void (int i, int j);
int main()
{
int d[N], n, dp[N][N],Case=0;
while (scanf("%d", &n) && n)
{
Case++;
int i, k;
scanf("%d%d", &d[0], &d[1]);
for (i = 2; i <= n; i++)
scanf("%*d%d", &d[i]);
for (i = 0; i <= n; i++)
for (k = 0; k <= n; k++)
dp[i][k] = 1e9;
for (i = 1; i <= n; i++)
dp[i][i] = 0;
for (int dia = 1; dia < n; dia++)
{
for (i = 1; i <= n - dia; i++)
{
int j = i + dia;
for (k = i; k < j; k++)
{
int cost = dp[i][k] + dp[k + 1][j] + d[i - 1] * d[k] * d[j];
if (cost < dp[i][j])
{
path[i][j] = k;
dp[i][j] = cost;
}
}
}
}
printf("Case %d: ",Case);
output(1, n);
putchar('n');
}
return 0;
}
void (int i, int j)
{
if (i == j)
printf("A%d", i);
else
{
int mid = path[i][j];
putchar('(');
output(i, mid);
printf(" x ");
output(mid + 1,j);
putchar(')');
}
}
|
近期评论