P4544 题解

· · 题解

介于本人太蠢，至死没有想出 O(NK) 解法，于是我们有了 O(NK\log K) 解法（

1.O(N^2K^2)

设 f_{i, k} 表示当前在第 i 家商店，饲料数恰好为 k 的最小代价。

考虑几个因素：

于是得到最朴素的方程：

f_{i, p + k} = \min\bigg(f_{j, k} + k^2(X_i - X_j) + C_i \times p\bigg) 
// 75 pts
for(int i = 1; i <= N; ++ i)
        for(int p = 0; p <= a[i].f; ++ p)
            for(int k = 0; k + p <= K; ++ k)
                for(int j = 0; j < i; ++ j)
                    f[i][k + p] = min(f[i][k + p], f[j][k] + sq(k) * (a[i].x - a[j].x) + a[i].c * p);

2.O(N^2K + NK^2)

我们发现在上述转移方程中，只有最后一项含有 p。

不妨设 g_{i, k} = \min\bigg(f_{j, k}+ k^2(X_i - X_j) \bigg)，则 f_{i, p + k} = \min(g_{i, k}) + C_i \times p。

其中 g_{i, k} 可以 O(NK) 预处理，f_{i, p + k} 可以 O(K^2) 转移。

// 90 pts
for(int i = 1; i <= N; ++ i) {
    memset(g, 0x3f, sizeof g);
    for(int k = 0; k <= K; ++ k) {
        for(int j = 0; j < i; ++ j) {
            g[k] = min(g[k], f[j][k] + sq(k) * (a[i].x - a[j].x));
        }
    }
    for(int p = 0; p <= a[i].f; ++ p) {
        for(int k = 0; k + p <= K; ++ k) 
            f[i][p + k] = min(f[i][p + k], g[k] + ll(p) * a[i].c);
    }
}

3.O(N^2K)

把关于 i 的式子从 g_{i, k} 中去除，重新定义 g_{i, k} = \min\bigg(f_{j, k}- k^2\times X_j \bigg)

这样的好处在于 g_{i, k} = \min(g_{i - 1, k},\ f_{i - 1, k} - k^2 \times X_{i - 1}) 是可以 O(K) 递推的。

// 90 pts
for(int i = 1; i <= N; ++ i) {
    for(int p = 0; p <= a[i].f; ++ p) {
        for(int k = 0; k + p <= K; ++ k) 
            f[i][p + k] = min(f[i][p + k], g[k] + sq(k) * a[i].x +  ll(p) * a[i].c);
    }
    for(int k = 0; k <= K; ++ k) {
        g[k] = min(g[k], f[i][k] - sq(k) * a[i].x);
    }
}

4.O(NK\log K)

观察上述代码，复杂度瓶颈在于第一个循环。

不要枚举 k, p，直接枚举 j = k + p，那么会变成这样：

for(int j = 0; j <= K; ++ j) {
    for(int k = j; j - k <= a[i].f; -- k)       // k \in [j - a[i].f ,j] 
        f[i][j] = min(f[i][j], (g[k] + sq(k) * a[i].x - (ll)k * a[i].c) + (ll)j * a[i].c);
}

也就是

f_{i, j} = j \times C_i + \min\bigg( g_k + k^2 \times X_i - k \times C_i \bigg) \quad k \in [j - F_i, j]

后面的式子只关于 i, k，且是连续的一段，线段树维护区间最值。

#include<bits/stdc++.h>
#define eb emplace_back
#define sq(x) (ll(x) * (x))
using namespace std;

using ll = long long;

int K, E, N;
ll f[505][10005], g[10005];

struct Node {
    int x, f; ll c;
    bool operator < (const Node &o) const {
        return x < o.x;
    }
} a[505];

ll t[400020];

#define ls x << 1
#define rs ls | 1

void init(int i, int x = 1, int l = 0, int r = K) {
    if(l == r) {
        t[x] = g[l] + sq(l) * a[i].x - l * a[i].c;
        return;
    }
    int mid = l + r >> 1;
    init(i, ls, l, mid), init(i, rs, mid + 1, r);
    t[x] = min(t[ls], t[rs]);
}

ll query(int L, int R, int x = 1, int l = 0, int r = K) {
    if(L > R) return 2e18;
    if(L <= l && r <= R) return t[x];
    int mid = l + r >> 1;
    ll ret = 2e18;
    if(L <= mid) ret = min(ret, query(L, R, ls, l, mid));
    if(R > mid) ret = min(ret, query(L, R, rs, mid + 1, r));
    return ret;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> K >> E >> N;
    for(int i = 1; i <= N; ++ i) {
        cin >> a[i].x >> a[i].f >> a[i].c;
    }
    sort(a + 1, a + N + 1);
    a[++ N].x = E;
    memset(f, 0x3f, sizeof f), memset(g, 0x3f, sizeof g);
    f[0][0] = 0;
    g[0] = 0;
    for(int i = 1; i <= N; ++ i) {
        init(i);
        for(int j = 0; j <= K; ++ j) {
            f[i][j] =query(max(j - a[i].f, 0), j) + (ll)j * a[i].c;
        }
        for(int k = 0; k <= K; ++ k) {
            g[k] = min(g[k], f[i][k] - sq(k) * a[i].x);
        }
    }
    cout << f[N][K];
    return 0;
}