C++ Library for Competitive Programming
View the Project on GitHub emthrm/cp-library
/* * @title 動的計画法/Knuth–Yao speedup * * verification-helper: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415 */ #include <iostream> #include <limits> #include <vector> #include "emthrm/dynamic_programming/knuth_yao_speedup.hpp" // 二分探索木のコスト \sum_{i = 1}^N w_i * depth(i) の最小値 int main() { int n; std::cin >> n; std::vector<std::vector<long long>> w(n, std::vector<long long>(n)); for (int j = 0; j < n; ++j) { std::cin >> w.front()[j]; if (j > 0) [[likely]] w.front()[j] += w.front()[j - 1]; } for (int i = 1; i < n; ++i) { for (int j = i; j < n; ++j) { w[i][j] = w.front()[j] - w.front()[i - 1]; } } std::cout << emthrm::knuth_yao_speedup( w, std::numeric_limits<long long>::max())[0][n - 1] << '\n'; return 0; }
#line 1 "test/dynamic_programming/knuth_yao_speedup.test.cpp" /* * @title 動的計画法/Knuth–Yao speedup * * verification-helper: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415 */ #include <iostream> #include <limits> #include <vector> #line 1 "include/emthrm/dynamic_programming/knuth_yao_speedup.hpp" #include <algorithm> #line 6 "include/emthrm/dynamic_programming/knuth_yao_speedup.hpp" namespace emthrm { template <typename T> std::vector<std::vector<T>> knuth_yao_speedup( const std::vector<std::vector<T>>& w, const T inf) { const int n = w.size(); std::vector<std::vector<T>> dp(n, std::vector<T>(n, inf)); if (n == 0) [[unlikely]] return dp; std::vector<std::vector<int>> argmin(n, std::vector<int>(n, -1)); for (int j = 0; j < n; ++j) { dp[j][j] = 0; argmin[j][j] = j; for (int i = j - 1; i >= 0; --i) { const int right = std::min(j - 1, argmin[i + 1][j]); for (int k = argmin[i][j - 1]; k <= right; ++k) { const T tmp = dp[i][k] + dp[k + 1][j]; if (tmp < dp[i][j]) { dp[i][j] = tmp; argmin[i][j] = k; } } dp[i][j] += w[i][j]; } } return dp; } } // namespace emthrm #line 12 "test/dynamic_programming/knuth_yao_speedup.test.cpp" // 二分探索木のコスト \sum_{i = 1}^N w_i * depth(i) の最小値 int main() { int n; std::cin >> n; std::vector<std::vector<long long>> w(n, std::vector<long long>(n)); for (int j = 0; j < n; ++j) { std::cin >> w.front()[j]; if (j > 0) [[likely]] w.front()[j] += w.front()[j - 1]; } for (int i = 1; i < n; ++i) { for (int j = i; j < n; ++j) { w[i][j] = w.front()[j] - w.front()[i - 1]; } } std::cout << emthrm::knuth_yao_speedup( w, std::numeric_limits<long long>::max())[0][n - 1] << '\n'; return 0; }