题目大意：给你一排卡片，你可以从从中抽一些卡片（但是不能抽最左和最右的卡片），每张卡片上有一个数字，当你从中抽出一张卡片后，你将得卡片的数字和卡片左右两张卡片的数字的乘积的分数，问当剩下最左和最右两张卡片的时候，你可以得到的最小的分数？
这一题一看好像挺复杂的，但是如果我们换一个思维方式，这一题就会变得很熟悉
首先这一题是显而易见的DP（找最小值，不能取极限方式）
首先他要我们抽卡片是吧，一开始我们可能会想到先抽一张看看，然后在扫一遍其他卡片看能否抽，但是这样带来的直接后果就是，我们很难对先前我们抽过的卡片进行分数的储存，那么可以这么想，如果我们在抽卡片之前，把左i张右j张的卡片的抽取已经记下来了（相当于是抽空了），然后我们再把这张卡片和i-1和j+1的卡片的乘积+左i张和右j张卡片的分数加起来不就等于我们当前抽的卡片的分数了吗！那么最后我们就可以维护一个最小值区间，把区间不断扩大到n-2（除掉最左和最右两张），那得出的值即是最后的最小分数
而这个方法，正是矩阵乘法的顺序安排的思路，熟悉而亲切
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 5 static long long cards[100]; 6 static long long dp[100][100]; 7 8 void Search(const int); 9 long long min(const long long, const long long); 10 11 int main(void) 12 { 13 int N, i; 14 while (~scanf("%d", &N)) 15 { 16 for (i = 0; i < N; i++) 17 scanf("%d", &cards[i]); 18 //memset(dp, 0, sizeof(dp)); 19 Search(N); 20 } 21 return 0; 22 } 23 24 long long min(const long long x, const long long y) 25 { 26 return x < y ? x : y; 27 } 28 29 void Search(const int N) 30 { 31 int i, j, k, pos; 32 33 for (i = 1; i < N - 1; i++) 34 dp[i][i] = cards[i - 1] * cards[i] * cards[i + 1]; 35 for (k = 1; k < N - 2; k++) 36 { 37 for (i = 1; i < N - 1 - k; i++) 38 { 39 pos = i + k; 40 dp[i][pos] = cards[i] * cards[i - 1] * cards[pos + 1] + dp[i + 1][pos];//注意cards的位置 41 for (j = i + 1; j < pos; j++) 42 { 43 dp[i][pos] = min(dp[i][pos], 44 cards[j] * cards[i - 1] * cards[pos + 1] + dp[i][j - 1] + dp[j + 1][pos]); 45 } 46 dp[i][pos] = min(dp[i][pos], cards[i - 1] * cards[pos] * cards[pos + 1] + dp[i][pos - 1]); 47 } 48 } 49 printf("%lld ", dp[1][N - 2]); 50 }