From 2088bf7f12f583b37615969bed9747c6c2678e69 Mon Sep 17 00:00:00 2001
From: Santo Cariotti <santo@dcariotti.me>
Date: Sat, 21 Jan 2023 18:42:00 +0100
Subject: add matrix

---
 Year_2/Algorithms/matrix-chain.cc | 75 +++++++++++++++++++++++++++++++++++++++
 1 file changed, 75 insertions(+)
 create mode 100644 Year_2/Algorithms/matrix-chain.cc

(limited to 'Year_2/Algorithms')

diff --git a/Year_2/Algorithms/matrix-chain.cc b/Year_2/Algorithms/matrix-chain.cc
new file mode 100644
index 0000000..2b87082
--- /dev/null
+++ b/Year_2/Algorithms/matrix-chain.cc
@@ -0,0 +1,75 @@
+#include <fstream>
+#include <iostream>
+#include <vector>
+#define INF 9999999
+
+using namespace std;
+
+using pii = pair<int, int>;
+
+int
+matrix_chain_multiply(vector<pii> a)
+{
+    int n = a.size();
+    int i, d, k;
+
+    int** m = new int*[n];
+
+    for (i = 0; i < n; ++i)
+        m[i] = new int[n];
+
+    for (i = 0; i < n; ++i)
+        m[i][i] = 0;
+
+    for (d = 1; d < n; ++d) {
+        for (i = 1; i < n - d; ++i) {
+            int j = d + i;
+            m[i][j] = INF;
+
+            for (k = i; k < j; ++k) {
+                int q = m[i][k] + m[k + 1][j] + a[i - 1].first * a[k].first * a[j].first;
+                if (q < m[i][j])
+                    m[i][j] = q;
+            }
+        }
+    }
+
+    int result = m[1][n - 1];
+
+    for (i = 0; i < n; ++i)
+        delete[] m[i];
+
+    delete[] m;
+
+    return result;
+}
+
+int
+main(int argc, char** argv)
+{
+    int ts = (argc > 1) ? stoi(argv[1]) : 100;
+    ifstream fin("input.txt");
+    ofstream fout("output.txt");
+    string ch;
+
+    for (int i = 0; i < ts; ++i) {
+        vector<pii> v;
+        int n, x1, x2 {};
+        fin >> n;
+
+        for (int j = 0; j < n; ++j) {
+            fin >> ch;
+            auto x = ch.find('x');
+            x1 = stoi(ch.substr(1, x - 1));
+            x2 = stoi(ch.substr(x + 1, ch.length() - 1));
+            v.push_back({ x1, x2 });
+        }
+        v.push_back({ x2, 0 });
+        fout << matrix_chain_multiply(v) << endl;
+    }
+
+    fin.close();
+    fout.close();
+
+    return 0;
+}
-- 
cgit v1.2.3-18-g5258