test/dp/knuth_merge.test.cpp

• View this file on GitHub
• Last update: 2024-11-09 00:49:07+00:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415

Depends on

• dp/knuth_merge.hpp
• prelude.hpp

Code

// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415

#include "dp/knuth_merge.hpp"

int k, n;
ll w[4000], sum[4001];

int main() {
  scanf("%d", &n);
  rep(i, n) scanf("%lld", w+i);
  rep(i, n) sum[i+1] = sum[i] + w[i];
  auto ans = knuth_merge_dp(n, [](int l, int r) { return sum[r] - sum[l]; });
  printf("%lld\n", ans[0][n]);
}

#line 1 "test/dp/knuth_merge.test.cpp"
// competitive-verifier: PROBLEM https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2415

#line 2 "prelude.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vc = vector<char>;
#define rep2(i, m, n) for (auto i = (m); i < (n); i++)
#define rep(i, n) rep2(i, 0, n)
#define repr2(i, m, n) for (auto i = (n); i-- > (m);)
#define repr(i, n) repr2(i, 0, n)
#define all(x) begin(x), end(x)
auto ndvec(int n, auto e) { return vector(n, e); }
auto ndvec(int n, auto ...e) { return vector(n, ndvec(e...)); }
auto comp_key(auto&& f) { return [&](auto&& a, auto&& b) { return f(a) < f(b); }; }
auto& max(const auto& a, const auto& b) { return a < b ? b : a; }
auto& min(const auto& a, const auto& b) { return b < a ? b : a; }
#if __cpp_lib_ranges
namespace R = std::ranges;
namespace V = std::views;
#endif
#line 3 "dp/knuth_merge.hpp"

// O(n^2)
// Starts with dp(l, r) = 0 (r - l <= 1) and
// dp(l, r) = min { dp(l, k) + dp(k, r) + cost(l, r) : l < k < r }
// Requires cost(b,c) <= cost(a,d) and
//          cost(a,c) + cost(b,d) <= cost(a,d) + cost(b,c)
// for a < b < c < d (wider is worse).
template <class F>
auto knuth_merge_dp(int n, F cost) {
  using T = decltype(cost(0, 0));
  vector<vector<T>> dp(n + 1, vector<T>(n + 1, numeric_limits<T>::max() / 2));
  vector<int> opt(n + 2), opt2(n + 2);
  repr(k, n + 1) {
    dp[k][k] = T(0), opt[k] = k;
    if (k + 1 <= n) dp[k][k + 1] = T(0);
    rep2(i, k + 2, n + 1) rep2(j, max(k + 1, opt2[i - 1]), min(i, opt[i] + 1)) {
      if (dp[k][i] > dp[k][j] + dp[j][i] + cost(k, i))
        dp[k][i] = dp[k][j] + dp[j][i] + cost(k, i), opt2[i] = j;
    }
    swap(opt, opt2);
  }
  return dp;
}
#line 4 "test/dp/knuth_merge.test.cpp"

int k, n;
ll w[4000], sum[4001];

int main() {
  scanf("%d", &n);
  rep(i, n) scanf("%lld", w+i);
  rep(i, n) sum[i+1] = sum[i] + w[i];
  auto ans = knuth_merge_dp(n, [](int l, int r) { return sum[r] - sum[l]; });
  printf("%lld\n", ans[0][n]);
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-12	testcase_00	AC	79 ms	8 MB
g++-12	testcase_01	AC	13 ms	8 MB
g++-12	testcase_02	AC	12 ms	8 MB
g++-12	testcase_03	AC	12 ms	8 MB
g++-12	testcase_04	AC	12 ms	8 MB
g++-12	testcase_05	AC	13 ms	8 MB
g++-12	testcase_06	AC	13 ms	8 MB
g++-12	testcase_07	AC	13 ms	8 MB
g++-12	testcase_08	AC	12 ms	8 MB
g++-12	testcase_09	AC	12 ms	8 MB
g++-12	testcase_10	AC	12 ms	8 MB
g++-12	testcase_11	AC	12 ms	8 MB
g++-12	testcase_12	AC	12 ms	8 MB
g++-12	testcase_13	AC	13 ms	8 MB
g++-12	testcase_14	AC	13 ms	8 MB
g++-12	testcase_15	AC	12 ms	8 MB
g++-12	testcase_16	AC	12 ms	8 MB
g++-12	testcase_17	AC	12 ms	8 MB
g++-12	testcase_18	AC	12 ms	8 MB
g++-12	testcase_19	AC	13 ms	8 MB
g++-12	testcase_20	AC	13 ms	8 MB
g++-12	testcase_21	AC	13 ms	8 MB
g++-12	testcase_22	AC	13 ms	8 MB
g++-12	testcase_23	AC	160 ms	54 MB
g++-12	testcase_24	AC	158 ms	54 MB
g++-12	testcase_25	AC	584 ms	153 MB
g++-12	testcase_26	AC	581 ms	153 MB
g++-12	testcase_27	AC	524 ms	153 MB
g++-12	testcase_28	AC	527 ms	153 MB
g++-12	testcase_29	AC	548 ms	153 MB
g++-12	testcase_30	AC	559 ms	153 MB
g++-12	testcase_31	AC	559 ms	153 MB
g++-12	testcase_32	AC	560 ms	152 MB
g++-12	testcase_33	AC	582 ms	153 MB
g++-12	testcase_34	AC	586 ms	153 MB
g++-12	testcase_35	AC	581 ms	153 MB
g++-12	testcase_36	AC	581 ms	152 MB
g++-12	testcase_37	AC	547 ms	153 MB
g++-12	testcase_38	AC	578 ms	153 MB
g++-12	testcase_39	AC	574 ms	153 MB
g++-12	testcase_40	AC	533 ms	152 MB
g++-12	testcase_41	AC	585 ms	152 MB
g++-12	testcase_42	AC	635 ms	153 MB
g++-12	testcase_43	AC	652 ms	153 MB

Back to top page