文档介绍：?最大矩阵连乘次数描述给定 n个矩阵{ A1,A2, …,An },其中 Ai与 Ai+1 是可乘的, i=1,2 , …,n-1 。如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最大。输入输入包含多组测试数据。第一行为一个整数 C,表示有 C组测试数据, 接下来有 2*C行数据,每组测试数据占 2行,每组测试数据第一行是 1 个整数 n(n ≤ 10) ,表示有 n个矩阵连乘,接下来一行有 n+1 个数,表示是 n个矩阵的行及第 n个矩阵的列,它们之间用空格隔开。输出你的输出应该有 C行,即每组测试数据的输出占一行,它是计算出的矩阵最大连乘积次数。样例输入 13 10 100 5 50 样例输出 75000 ?分析一个 A*B的矩阵和一个 B*C的矩阵相乘所需要的乘法次数是 A*B*C次,得到的矩阵是 A*C的。在运算的最后一步,总是由两部分来合成一个矩阵,因此我们只要枚举这一步,即可转到相应的子结构中去。我们定义 dfs (x,y) 表示第 x个矩阵到第 y个矩阵相乘所能够达到的最多次数。于是我们可以知道如下方程: 其中 T[x,k ]* T[k+1,y] 表示最后一步所需要的乘法次数。?#include < iostream > using namespace std; int p[15], q[15]; int DFS(int x, int y){ int max = 0, temp, i; if(x == y) return 0; for(i =x; i<=y-1; i++) { temp = DFS(x , i)+ DFS(i+1, y)+ p[x ]* q[i ]* q[y ]; if(temp > max) max = temp; } return max; } int main(){ int a, s[15], i, n; cin >> n; while(n --){ cin >> a; for(i =0; i<=a; i++) cin >> s[i ]; for(i =1; i<=a; i++){ p[i ]= s[i-1]; q[i ]= s[i ]; } cout << DFS(1, a) << endl ;} return 0; } ?石子归并描述有n堆石子排成一条直线,每堆石子有一定的重量。现在要合并这些石子成为一堆石子,但是每次只能合并相邻的两堆。每次合并需要消耗一定的体力,该体力为所合并的两堆石子的重量之和。问最少需要多少体力才能将 n堆石子合并成一堆石子? 输入输入只包含若干组数据。每组数据第一行包含一个正整数 n(2<=n<=100) ,表示有 n堆石子。接下来一行包含 n个正整数 a1,a2,a3,...,an ( 0< ai <=100 , 1<=i<=n )。输出对应输入的数据,每行输出消耗的体力。样例输入 2 47 95 样例输出 142 分析我们很容易想到用贪心的想法解决,但是用贪心解题算法错误。因为不一定最小的合并在一起就可以保证最终结果是最小的。最后合并成一对石子,是由两堆石子合并而来,不妨这样定义状态转移方程: 设F [i,j]表示从第 i堆到第 j堆石子数总和。 Fmin(i,j )表示将从第 i堆石子合并到第 j堆石子的最小的得分?#include < iostream > using namespace std; int main(){ int a, q[110], i, j, s[110][110], r,k, p[110][110]; while(cin >> a){ for(i =1; i<=a; i++) cin >> q[i ]; memset(s , 0, sizeof(s )); for(i =1; i<=a; i++) { p[i][i ]= q[i ]; for(j =i+1; j<= a;j ++) p[i][j ]= p[i][j-1] + q[j ]; } for(r =2; r<=a; r++){ for(i =1; i<=a-r+1; i++) {j=i+r- 1; s[i][j ]= INT_MAX; for(k =i; k<j; k++) { if(s[i][j ]> s[i][k ]+ s[k+1][j] + p[i][j ]) ? s[i][j ]= s[i][k ]+ s[k+1][j] + p[i][j ]; }}} cout << s[1][a] << endl ;} return 0; } ?滑雪 Michael 喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。 Michael 想知道载一个区域中