3
10 100
100 5
5 50
7500
一道区间DP题，根据矩阵乘的定义，参与复杂度计算的只有n+1个数，第一个矩阵的行数和列数，接下来n-1个矩阵的列数，这n+1个数存入一个数组a[]。
状态转移方程：f[i][k] = min{f[i][j] + f[j][k] + a[i]*a[j]*a[k]}
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 using namespace std; 5 const int N = 109; 6 int n; 7 int a[N], f[N][N]; 8 int main() 9 { 10 scanf("%d", &n); 11 scanf("%d%d", &a[1], &a[2]); 12 for(int i = 2; i <= n; i++) 13 { 14 int x; 15 scanf("%d%d", &x, &a[i+1]); 16 } 17 memset(f, 0x3f, sizeof(f)); 18 for(int i = 1; i <= n; i++) 19 f[i][i] = 0, f[i][i+1] = 0; 20 for(int j = 1; j <= n+1; j++) 21 for(int i = 1; i + j - 1 <= n+1; i++) 22 { 23 int r = i + j - 1; 24 for(int k = i + 1; k < r; k++) 25 f[i][r] = min(f[i][r], f[i][k] + f[k][r] + a[i] * a[k] * a[r]); 26 } 27 printf("%d\n", f[1][n+1]); 28 return 0; 29 }
原文：https://www.cnblogs.com/Jony-English/p/12488950.html
