题目大意：有一个正整数序列，从中间（不是第一个数和最后一个数）拿出一个数，可以得到一个分值，分值计算规则为：这个数乘以它左边的数和它右边的数。重复以上步骤，直至剩下第一个数和最后一个数，计算可以得到的最小分值。
实际上是矩阵链乘问题的另一种表述方式，很不错的题，开始的时候一点没看出来，网上搜素时别人直接说是矩阵链乘，一想还真是，完全是按这个模型构造的问题啊
1 #include <cstdio> 2 #include <climits> 3 #define MAXN 110 4 5 int p[MAXN], m[MAXN][MAXN]; 6 7 int main() 8 { 9 #ifdef LOCAL 10 freopen("in", "r", stdin); 11 #endif 12 int N; 13 while (scanf("%d", &N) != EOF) 14 { 15 int n = N - 1; // n is the number of matrixes 16 for (int i = 0; i <= n; i++) scanf("%d", &p[i]); 17 for (int i = 1; i <= n; i++) m[i][i] = 0; 18 for (int l = 2; l <= n; l++) 19 { 20 for (int i = 1; i <= n-l+1; i++) 21 { 22 int j = i+l-1; 23 m[i][j] = INT_MAX; 24 for ( int k = i; k <= j-1; k++) 25 { 26 int q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]; 27 if (q < m[i][j]) m[i][j] = q; 28 } 29 } 30 } 31 printf("%d ", m[1][n]); 32 } 33 return 0; 34 }