# 10203. Fast Matrix Chain Multiplication Basic (OpenMP)

## 題目描述

$$ABCD=(AB)(CD)=A(BCD)=A(BC)D=...$$

$(AB)C$ 有 $(10\times 30\times 5)+(10\times 5\times 60)=1500+3000=4500$ 個運算

$A(BC)$ 有 $(30\times 5\times 60)+(10\times 30\times 60)=9000+18000=27000$ 個運算

### sequence.c

12345678910111213141516171819202122232425262728#include <stdio.h>#define MAXN 2048#define INF (1LL<<60)int N;long long dp[MAXN*MAXN], SZ[MAXN+1];int main() {    while (scanf("%d", &N) == 1) {        for (int i = 0; i <= N; i++)            scanf("%lld", &SZ[i]);        for (int i=0; i<N; i++)            dp[i*N + i] = 0;         for (int i = 1; i < N; i++) {            for (int j = 0; j < N-i; j++) {                int l = j, r = j+i;                long long local = INF;                for (int k = l; k < r; k++) {                    long long t = dp[l*N+k] + dp[(k+1)*N+r] + SZ[l] * SZ[k+1] * SZ[r+1];                    if (t < local)                        local = t;                }                dp[l*N+r] = local;            }        }        printf("%lld\n", dp[0*N+N-1]);    }    return 0;}


## 輸入格式

• $1 \le N \le 2048$
• $1 \le Z_i \le 4096$

## 範例輸入

22 2 2310 30 5 6031 5 20 135 10 20 35630 35 15 5 10 20 25


## 範例輸出

84500105450015125