dp-矩阵连乘
escription
两个矩阵A(r行s列)和B(s行t列)相乘, 乘法代价为rst. 现给定N(N<=500)个矩阵连乘问题, 请计算最小乘法代价。
Input
第一行输入M(M<=10)表示有M组数据。每组数据第一行输入N，表示矩阵个数；接下来一行输入N个矩阵的行数和列数。
Output
输出M行正整数，第i行表示第i组数据的最小乘法代价。
Sample Input
2
3
1 2 2 3 3 4
3
4 3 3 2 2 1
Sample Output
18
18
#include "iostream"
#include "cstring"using namespace std;const int N = 510;
int f[N][N];int row[N];
int col[N];int getResult(int n) {memset(f, 0x3f, sizeof f);for (int i = 0; i <= n; ++i) {f[i][i] = 0;}for (int len = 2; len <= n; ++len) {for (int i = 1; i <= n; ++i) { //int j = i + len - 1;if (j <=n){ // 前两个循环，枚举区间// 第3个循环，枚举决策，即在哪里断开for (int k = i; k < j; ++k) {f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]+row[i]*col[k]*col[j]);}}}}return f[1][n];
}int main() {int M;cin >> M;while (M--) {int n;cin >> n;for (int i = 1; i <= n; ++i) {cin >> row[i] >> col[i];}cout << getResult(n)<<endl;}
}