#line 1 "test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/952" #include using namespace std; #line 4 "https://drken1215.github.io/algorithm/Others/int128.hpp.html" using namespace std; // int 128 using i128 = __int128; i128 to_integer(const string &s) { i128 res = 0; for (auto c : s) { if (isdigit(c)) res = res * 10 + (c - '0'); } if (s[0] == '-') res *= -1; return res; } istream& operator >> (istream &is, i128 &x) { string s; is >> s; x = to_integer(s); return is; } ostream& operator << (ostream &os, const i128 &x) { i128 ax = (x >= 0 ? x : -x); char buffer[128]; char *d = end(buffer); do { d--; *d = "0123456789"[ax % 10]; ax /= 10; } while (ax != 0); if (x < 0) { d--; *d = '-'; } int len = end(buffer) - d; if (os.rdbuf()->sputn(d, len) != len) { os.setstate(ios_base::badbit); } return os; } template , int> = 0> constexpr i128 abs(T x) { return x < 0 ? -x : x; } constexpr i128 gcd(i128 a, i128 b) { while (b != 0) { i128 c = a % b; a = b, b = c; } return abs(a); } // uint 128 using u128 = __uint128_t; u128 to_uinteger(const string &s) { u128 res = 0; for (auto c : s) { if (isdigit(c)) res = res * 10 + (c - '0'); } return res; } istream& operator >> (istream &is, u128 &x) { string s; is >> s; x = to_uinteger(s); return is; } ostream& operator << (ostream &os, const u128 &x) { u128 ax = x; char buffer[128]; char *d = end(buffer); do { d--; *d = "0123456789"[ax % 10]; ax /= 10; } while (ax != 0); if (x < 0) { d--; *d = '-'; } int len = end(buffer) - d; if (os.rdbuf()->sputn(d, len) != len) { os.setstate(ios_base::badbit); } return os; } #line 4 "https://drken1215.github.io/algorithm/Optimization/monotone_convex_hull_trick.hpp.html" using namespace std; // Convex Hull Trick /* 追加クエリの直線の傾きが単調減少の場合 - insert(a, b): add y = ax + b, O(1) - query(x): min_i{a[i]*x + b}, O(log N) - query_monotone(x): min_i{a[i]*x + b}, O(1), x も単調増加であることを仮定 */ template struct MonotoneConvexHullTrick { using Line = pair; deque lines; T INF; MonotoneConvexHullTrick(T inf = numeric_limits::max() / 2) : INF(inf) {} bool check(const Line &a, const Line &b, const Line &c) { return (b.first - a.first) * (c.second - b.second) >= (b.second - a.second) * (c.first - b.first); } T get(int k, T x) { if (lines.empty() || k >= lines.size()) return INF; assert(k >= 0 && k < lines.size()); return lines[k].first * x + lines[k].second; } void insert(T a, T b) { Line l(a, b); while (lines.size() >= 2 && check(lines[(int)lines.size()-2], lines[(int)lines.size()-1], l)) { lines.pop_back(); // 不要な直線を捨てる } lines.push_back(l); } T query(T x) { int low = -1, high = (int)lines.size(); while (high - low > 1) { int mid = (low + high) / 2; if (get(mid, x) >= get(mid + 1, x)) low = mid; else high = mid; } return get(high, x); } // クエリの単調性も成り立つ場合 (x が単調増加) T query_monotone(T x) { while (lines.size() >= 2 && get(0, x) >= get(1, x)) lines.pop_front(); if (lines.empty()) return INF; return lines[0].first * x + lines[0].second; } }; #line 8 "test.cpp" // yukicoder No.952 危険な火薬庫 /* 末尾にドアを追加する。 ノード 0, 1, ..., N, N+1 f(i, j) = (S[j-1] - S[i])^2 選ぶドアが k 個 → 区間の個数は、N+1-k */ int main() { int N; cin >> N; N++; vector A(N, 0), S(N+1, 0); for (int i = 0; i < N; i++) { if (i) cin >> A[i]; S[i+1] = S[i] + A[i]; } vector chts(N+1, MonotoneConvexHullTrick()); i128 INF = i128(1)<<100; vector dp(N+1, vector(N+1, INF)); auto push = [&](int i, int j) -> void { if (i-1 >= 0) chts[i-j].insert(-S[i]*2, S[i]*S[i] + dp[i-1][j]); }; dp[0][0] = 0; push(0, 0); for (int i = 1; i <= N; i++) { for (int j = 0; j < i; j++) { dp[i][j] = min(dp[i][j], dp[i-1][j]); dp[i][j] = min(dp[i][j], chts[i-j].query_monotone(S[i]) + S[i] * S[i]); push(i, j); } } for (int k = 1; k < N; k++) { cout << dp[N][k] << endl; } }