From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 27 Jun 2022 17:19:28 +0200
Subject: updated tcr

---
 other/knuth.cpp | 15 +++++++++++++++
 1 file changed, 15 insertions(+)
 create mode 100644 other/knuth.cpp

(limited to 'other/knuth.cpp')

diff --git a/other/knuth.cpp b/other/knuth.cpp
new file mode 100644
index 0000000..f47dbe0
--- /dev/null
+++ b/other/knuth.cpp
@@ -0,0 +1,15 @@
+ll calc(int n, int k, const vector<vector<ll>> &C) {
+	vector<vector<ll>> dp(k, vector<ll>(n, inf));
+	vector<vector<int>> opt(k, vector<int>(n + 1, n - 1));
+
+	for (int i = 0; i < n; i++) dp[0][i] = C[0][i];
+	for (int i = 1; i < k; i++) {
+		for (int j = n - 1; j >= 0; --j) {
+			opt[i][j] = i == 1 ? 0 : opt[i - 1][j];
+			for (int k = opt[i][j]; k <= min(opt[i][j + 1], j - 1); ++k) {
+				if (dp[i][j] <= dp[i - 1][k] + C[k + 1][j]) continue;
+				dp[i][j] = dp[i - 1][k] + C[k + 1][j];
+				opt[i][j] = k;
+	}}}
+	return dp[k - 1][n - 1];
+}
-- 
cgit v1.2.3