fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <climits>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. // 计算最小乘法量的函数
  8. pair<string, int> matrixChainOrder(const vector<pair<int, int>>& matrices) {
  9.     int n = matrices.size();
  10.  
  11.     // 创建一个二维数组来存储最小乘法量
  12.     vector<vector<int>> cost(n, vector<int>(n, 0));
  13.  
  14.     // 创建一个二维数组来存储最优括号位置
  15.     vector<vector<string>> brackets(n, vector<string>(n, ""));
  16.  
  17.     // 初始化cost和brackets数组
  18.     for (int len = 2; len < n; len++) {
  19.         for (int i = 0; i < n - len + 1; i++) {
  20.             int j = i + len - 1;
  21.             cost[i][j] = INT_MAX;
  22.  
  23.             for (int k = i; k < j; k++) {
  24.                 int q = cost[i][k] + cost[k + 1][j] + matrices[i].first * matrices[k].second * matrices[j].second;
  25.                 if (q < cost[i][j]) {
  26.                     cost[i][j] = q;
  27.                     brackets[i][j] = "(" + brackets[i][k] + brackets[k + 1][j] + ")";
  28.                 }
  29.             }
  30.         }
  31.     }
  32.  
  33.     // 返回最小乘法量和最优括号位置
  34.     return {brackets[0][n - 1], cost[0][n - 1]};
  35. }
  36.  
  37. int main() {
  38.     int n;
  39.     cin >> n;
  40.  
  41.     vector<pair<int, int>> matrices(n);
  42.     for (int i = 0; i < n; i++) {
  43.         cin >> matrices[i].first >> matrices[i].second;
  44.         cout << matrices[i].first << " than " << matrices[i].second << endl;
  45.     }
  46.  
  47.     pair<string, int> result = matrixChainOrder(matrices);
  48.  
  49.     cout << result.first << endl;
  50.     cout << result.second << endl;
  51.  
  52.     return 0;
  53. }
  54.  
Success #stdin #stdout 0s 5300KB
comments (?)
stdin 
4
2 3
3 4
4 2
2 5
stdout 
2 than 3
3 than 4
4 than 2
2 than 5

0
https://ideone.com/2DVmi8
language:
C++ (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!