TIOJ 1347：希爾伯特的書架

TIOJ 1347：希爾伯特的書架

題目大意：有 $N$ 本書想要放在書架上，每本書有一個寬度 $A_i$，可以選擇一段編號連續的書放在同一層，如果書本 $i$ 後面有書，那要間隔 $L_i$。給你 $K$ 跟 $P$，假設這層的總寬度是 $M$，那混亂度就是 $|M-K|^P$，問最小混亂度總和。

解法：可以用 $dp$ 解題，假設 $dp_i$ 是到 $1\sim i$ 的最小混亂度，$pre_i = \sum\limits^{i}_{j = 1} A_i + L_i$，那 $dp_i = \min\limits_{0\leq j < i} (dp_j + |pre_i - pre_j - L_i - K|^P)$。可以發現到隨著 $i$ 越大，轉移來源 $j$ 也會越大，於是可以用四邊形凸性優化，只是很有可能會超過 $\text{long long}$ 的範圍，所以可以用 $\text{double}$ 和除法判斷。複雜度 $O(N\times log(N)\times log(P))$。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for (int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e6 + 5;
const ll INF = 1e18;
const double dINF = log ((ll) INF);

struct Seg {int pos, l, r;};

int n, k, p;
int L[SIZE];
ll pre[SIZE], dp[SIZE];
Seg st[SIZE];
int sl = 1, sr;

ll power (ll d, int up) {
    ll ans = 1;
    while (up) {
        if (up & 1) {
            if (ans && INF / ans <= d) return INF;
            ans *= d;
        }
        if (d && INF / d <= d) d = INF;
        else d *= d;
        up >>= 1;
    }
    return ans;
}

double power (double d, int up) {
    double ans = 1;
    while (up--) ans *= d;
    return ans;
}

ll cal (int l, int r) {
    return dp[l] + power (abs (pre[r] - pre[l] - L[r] - k), p);
}

bool better (int x, int y, int r) {
    ll t1 = abs (pre[r] - pre[x] - L[r] - k), t2 = abs (pre[r] - pre[y] - L[r] - k);
    if (dp[x] <= dp[y] && t1 <= t2) return 1;
    if (dp[x] >= dp[y] && t1 >= t2) return 0;
    return dp[x] + power (1.00 * t1, p) <= dp[y] + power (1.00 * t2, p);
}

void solve() {
    cin >> n >> k >> p;
    FOR (i, 1, n) cin >> pre[i];
    for (int i = 1; i < n; i++) {
        cin >> L[i];
        pre[i] += pre[i - 1] + L[i];
    }
    pre[n] += pre[n - 1];
    st[++sr] = {0, 1, n};
    FOR (i, 1, n) {
        dp[i] = cal (st[sl].pos, i);
        if (st[sl].l == i) {
            if (st[sl].l == st[sl].r) sl++;
            else st[sl].l++;
        }
        while (sl <= sr && better (i, st[sr].pos, st[sr].l)) sr--;
        if (sl > sr) st[++sr] = {i, i + 1, n};
        else if (!better (i, st[sr].pos, st[sr].r)) {
            if (st[sr].r != n) {
                st[++sr] = {i, st[sr - 1].r + 1, n};
            }
        } else {
            auto [pos, l, r] = st[sr];
            while (l < r) {
                int mid = (l + r) / 2;
                if (better (i, pos, mid)) r = mid;
                else l = mid + 1;
            }
            st[sr].r = l - 1;
            st[++sr] = {i, l, n};
        }
    }
    cout << dp[n] << '\n';
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！