cp-problems

危険な火薬庫

解説

\(DP[i][j] =\)（ドア \(i\) まで見て，ドア \(i\) は開けずに \(j\) 個のドアを開けたときの火薬庫の危険度の最小値）とする．

\(\displaystyle S_i = \sum_{j \le i}A_j\) とすると，DP の遷移が以下のようになる．

\(\displaystyle DP[i + 1][j] = \min_{k\ge 0}(DP[i - k][j - k] + (S_{i} - S_{i - k}) ^ 2)\)

#include <iostream>
using namespace std;
using ll = long long;
const ll INF = 1e18;

int main() {
    int N;
    cin >> N;
    ll S[N + 1], DP[N + 2][N + 1];
    S[0] = 0;
    for (int i = 0; i < N; i++) cin >> S[i + 1], S[i + 1] += S[i];
    for (int i = 0; i < N + 2; i++) {
        for (int j = 0; j < N + 1; j++) DP[i][j] = INF;
    }
    DP[0][0] = 0;
    for (int i = 0; i < N + 1; i++) {
        for (int j = 0; j < N + 1; j++) {
            for (int k = 0; k < N + 2; k++) {
                if (i - k < 0 || j - k < 0) continue;
                ll cost = S[i] - S[i - k];
                DP[i + 1][j] = min(DP[i + 1][j], DP[i - k][j - k] + cost * cost);
            }
        }
    }
    for (int i = 0; i < N; i++) {
        cout << min(DP[N][i + 1], DP[N + 1][i + 1]) << endl;
    }
}

この DP を斜め（\(DP[i][j]\ \rightarrow DP[i + 1][j + 1] \ \rightarrow \cdots\)）に計算し，その計算に Convex Hull Trick を用いれば計算量 \(O(N^2)\) を達成できる．

#include <cmath>
#include <deque>
#include <iostream>
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;

struct ConvexHullTrick {
    using F = pair<ll, ll>;
    deque<F> deq;
#define a first
#define b second
#define lines deq.size()
    bool invalid_f1(F f0, F f1, F f2) {
        return (__int128) (f1.a - f0.a) * (f2.b - f1.b) >= (__int128) (f1.b - f0.b) * (f2.a - f1.a);
    }
    ll f(F f0, ll x) { return f0.a * x + f0.b; }
    void add(F f0) {
        while (lines >= 2 && invalid_f1(deq[lines - 2], deq[lines - 1], f0)) {
            deq.pop_back();
        }
        deq.push_back(f0);
    }
    ll min(ll x) {
        while (lines >= 2 && f(deq[0], x) >= f(deq[1], x)) {
            deq.pop_front();
        }
        return f(deq[0], x);
    }
#undef a
#undef b
#undef lines
};

int main() {
    int N;
    cin >> N;
    ll S[N + 1], DP[N + 2][N + 1];
    S[0] = 0;
    for (int i = 0; i < N; i++) cin >> S[i + 1], S[i + 1] += S[i];
    for (int i = 0; i < N + 2; i++) {
        for (int j = 0; j < N + 1; j++) DP[i][j] = INF;
    }
    for (int i = 0; i < N + 2; i++) DP[i][0] = 0;
    for (int i = 0; i < N + 2; i++) {
        ConvexHullTrick CHT;
        for (int j = 0; j < N + 1; j++) {
            if (i + j + 1 > N + 1) break;
            ll A = -2 * S[i + j], B = S[i + j] * S[i + j] + DP[i + j][j];
            ll X = S[i + j], Y = S[i + j] * S[i + j];
            CHT.add(make_pair(A, B));
            DP[i + j + 1][j] = min(DP[i + j + 1][j], CHT.min(X) + Y);
        }
    }
    for (int i = 0; i < N; i++) {
        cout << min(DP[N][i + 1], DP[N + 1][i + 1]) << endl;
    }
}