動的計画法/Knuth–Yao speedup
(test/dynamic_programming/knuth_yao_speedup.test.cpp)

• View this file on GitHub
• Last update: 2023-02-25 01:48:23+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415

Depends on

• Knuth–Yao speedup (include/emthrm/dynamic_programming/knuth_yao_speedup.hpp)

Code

/*
 * @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;
}

Back to top page