17网站模板,快速网页制作,自己做衣服的网站,wordpress本地备份矩阵链乘法问题的目标是找到最有效的方法来乘以给定的 n 个矩阵 M1,M2,M3,...,Mn。 编写一个程序#xff0c;读取 Mi 的维度#xff0c;并找到最小标量乘法以计算最大链链乘法 M1M2...Mn。
输入 在第一行中#xff0c;给出了一个整数 n。 在接下来的 n 行中#xff0c;矩阵…矩阵链乘法问题的目标是找到最有效的方法来乘以给定的 n 个矩阵 M1,M2,M3,...,Mn。 编写一个程序读取 Mi 的维度并找到最小标量乘法以计算最大链链乘法 M1M2...Mn。
输入 在第一行中给出了一个整数 n。 在接下来的 n 行中矩阵 Mi (i1...n) 的维度由两个整数 r 和 c 给出分别表示 Mi 的行数和列数。
输出 在一行中打印最小数量的标量乘法。
约束 1≤n≤100 1≤r,c≤100
输入样例 6 30 35 35 15 15 5 5 10 10 20 20 25 输出样例 15125 #include iostream
#include vector
#include algorithmusing namespace std;int main() {int n;cin n;//matrices直接存储一对数据vectorpairint, int matrices(n);for (int i 0; i n; i) {cin matrices[i].first matrices[i].second;}// 二维数组dp[i][j] 表示计算矩阵 Mi...Mj 所需的最小乘法次数vectorvectorint dp(n, vectorint(n, 0));for (int i 0; i n; i) {dp[i][i] 0;}//计算维度为 m x n 的矩阵 A 和 n x p 的矩阵 B 的乘积需要 m * n * p 次标量乘法//矩阵A (Mi 到 Mk 的乘积) 的维度//行数等于 Mi 的行数 (ri-1用 matrices[i].first 表示)//列数等于 Mk 的列数 (ck用 matrices[k].second 表示)//矩阵A的维度为 matrices[i].first x matrices[k].second//矩阵B (Mk1 到 Mj 的乘积) 的维度//行数等于 Mk1 的行数但由于矩阵是链式相乘Mk1的行数会等于Mk的列数//因此Mk1的行数等于ck即matrices[k].second//列数等于 Mj 的列数 (cj用 matrices[j].second 表示)//矩阵B的维度为matrices[k].second x matrices[j].secondfor (int len 2; len n; len) {for (int i 0; i n - len; i) {int j i len - 1;dp[i][j] 1e9; // 初始化为一个很大的值//循环遍历可能的分割点 kfor (int k i; k j; k) {int cost dp[i][k] dp[k 1][j] matrices[i].first * matrices[k].second * matrices[j].second;dp[i][j] min(dp[i][j], cost);}}}cout dp[0][n - 1] endl;return 0;
}
