hw4: add H4-5 & H4-6

tiankaima · Apr 12, 2024 · 0f46485 · 0f46485
1 parent 6c017df
commit 0f46485
Show file tree

Hide file tree

Showing 4 changed files with 104 additions and 0 deletions.
diff --git a/H4/H4-5.cpp b/H4/H4-5.cpp
@@ -0,0 +1,49 @@
+#include <iostream>
+#include <limits>
+
+int main()
+{
+    std::ios_base::sync_with_stdio(false);
+    std::cin.tie(nullptr);
+
+    int n;
+    std::cin >> n;
+
+    int* ps = new int[n + 1];
+
+    for (int i = 0; i < n; i++) {
+        std::cin >> ps[i] >> ps[i + 1];
+    }
+
+    int* m = new int[n * n];
+
+#define M(i, j) m[(i - 1) * n + (j - 1)]
+
+    for (int i = 1; i <= n; i++) {
+        M(i, i) = 0;
+    }
+
+    for (int l = 2; l <= n; l++) {
+        for (int i = 1; i <= n - l + 1; i++) {
+            int j = i + l - 1;
+
+            M(i, j) = std::numeric_limits<int>::max();
+            for (int k = i; k < j; k++) {
+//                std::cout << "M(" << i << "," << k << ")=" << M(i, k) << std::endl;
+//                std::cout << "M(" << k + 1 << "," << j << ")=" << M(k + 1, j) << std::endl;
+//                std::cout << "ps[" << i - 1 << "]=" << ps[i - 1] << std::endl;
+//                std::cout << "ps[" << k << "]=" << ps[k] << std::endl;
+//                std::cout << "ps[" << j << "]=" << ps[j] << std::endl;
+
+                M(i, j) = std::min(M(i, j), M(i, k) + M(k + 1, j) + ps[i - 1] * ps[k] * ps[j]);
+            }
+
+//            std::cout << "M(" << i << "," << j << ")=" << M(i, j) << std::endl;
+        }
+    }
+    std::cout << M(1, n) << std::endl;
+
+    delete[] ps;
+    delete[] m;
+    return 0;
+}
diff --git a/H4/H4-6.cpp b/H4/H4-6.cpp
@@ -0,0 +1,44 @@
+#include <iostream>
+#include <limits>
+
+int main()
+{
+    std::ios_base::sync_with_stdio(false);
+    std::cin.tie(nullptr);
+
+    int m, n;
+    std::cin >> m >> n;
+
+    int* map = new int[m * n];
+#define MAP(i, j) map[(i) * m + (j)]
+
+    for (int i = 0; i < m; i++) {
+        for (int j = 0; j < n; j++) {
+            std::cin >> MAP(i, j);
+        }
+    }
+
+    int* dp = new int[m * n];
+#define DP(i, j) dp[(i) * m + (j)]
+
+    int ans = 0;
+
+    for (int i = 0; i < m; i++) {
+        for (int j = 0; j < n; j++) {
+            if (i == 0 || j == 0) {
+                DP(i, j) = 1 - MAP(i, j);
+            } else if (MAP(i, j) == 1) {
+                DP(i, j) = 0;
+            } else {
+                DP(i, j) = std::min(DP(i - 1, j), std::min(DP(i, j - 1), DP(i - 1, j - 1))) + 1;
+            }
+            ans += DP(i, j);
+        }
+    }
+
+    std::cout << ans << std::endl;
+
+    delete[] map;
+    delete[] dp;
+    return 0;
+}
diff --git a/H4/input/H4-5.txt b/H4/input/H4-5.txt
@@ -0,0 +1,5 @@
+4
+20 5
+5 40
+40 50
+50 10
diff --git a/H4/input/H4-6.txt b/H4/input/H4-6.txt
@@ -0,0 +1,6 @@
+5 5
+1 0 0 0 0
+1 0 0 1 1
+0 1 0 0 0
+0 1 0 1 0
+1 0 0 0 0
-Original file line number
+Diff line change
@@ -0,0 +1,5 @@
+5
+40
+50
+10