hlg1600线性代数中的矩阵问题【区间dp】

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int maxn = 105;
 7 const int INF = 1000000000;
 8 
 9 int dp[maxn][maxn];
10 int a[maxn];
11 
12 int ddp(int i, int j) {
13     if(dp[i][j] != -1) return dp[i][j];
14     if(i + 1 == j) {
15         return  dp[i][j] = 0;
16     }
17     int Min = INF;
18     for(int k = i + 1; k < j; k++) {
19         Min = min(Min , ddp(i, k) + ddp(k, j) + a[i] * a[k] * a[j]);
20     }
21     return dp[i][j] = Min;
22 }
23 
24 int main() {
25     int t;
26     int n;
27     scanf("%d",&t);
28     while(t--) {
29         scanf("%d",&n);
30         for(int i = 1; i <= n + 1; i++) {
31             scanf("%d",&a[i]);
32         }
33         if(n == 1) {
34             puts("0");
35             continue;
36         }
37         memset(dp, -1, sizeof(dp));
38         printf("%d\n", ddp(1, n + 1));
39 //        for(int i = 1; i <= n + 1; i++) {
40 //            for(int j =1; j <= n + 1; j++) {
41 //                printf("%d %d %d\n", i, j, dp[i][j]);
42 //            }
43 
44     }
45     return 0;
46 }