Problem Solving►UVa

UVa 348 - Optimal Array Multiplication Sequence

Contents

  1. 1. Problem
  2. 2. Solution
  3. 3. Code

Problem

題目網址
中文網址

矩陣乘積鏈

Solution

學校剛好在教這部分呢~稍微注意一下 index 每次的邊界處理。
DP 的列式基本上就是判斷乘的順序看怎樣 cost 比較小:
dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k + 1][j] + d[i - 1] * d[k] * d[j])

Code

UVa 348UVa 348 - Optimal Array Multiplication Sequence
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
#include<cstdio>
#define N 11

int path[N][N];
void output(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])//ZJ的測資要改<=才會過....
                    {
                        path[i][j] = k;
                        dp[i][j] = cost;
                    }
                }
            }
        }

        printf("Case %d: ",Case);
        output(1, n);
        putchar('\n');
    }

    return 0;
}
void output(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(')');
    }
}