网站响应速度多少合适,网站模块建设中,莆田市荔城区建设局网站,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;
}
