「BZOJ 1597」土地购买 - 斜率优化 DP

农夫 John 准备扩大他的农场,他正在考虑 N 1 \leq N \leq 50000 )块长方形的土地。每块土地的长宽满足( 1 \leq 长、宽 \leq 1000000 )。每块土地的价格是它的面积,但 FJ 可以同时购买多快土地。这些土地的价格是它们最大的长乘以它们最大的宽,但是土地的长宽不能交换。如果 FJ 买一块 3 \times 5 的地和一块 5 \times 3 的地,则他需要付 5 \times 5 = 25 。FJ 希望买下所有的土地,但是他发现分组来买这些土地可以节省经费,他需要你帮助他找到最小的经费。

链接

BZOJ 1597

题解

考虑两块土地,若其中一块可将另一块完全包含,则可以将较小的一块忽略,因为它总是可以被和另一块同时购买,而不增加花费。

排序将上述情况筛除后,整个序列以一个关键字升序,另一个关键字降序。假设宽度 w(i) 降序,高度 h(i) 升序。设 f(i) 表示购买前 i 块土地的最小花费,考虑哪些不和 i 在一起购买。

f(i) = \min\limits_{j = 0} ^ {i - 1} \{ f(j) + w(j + 1) \times h(i) \}

斜率优化,考虑两个决策 a b ,若 a b 优,则有

\begin{align*} f(a) + w(a + 1) \times h(i) & < f(b) + w(b + 1) \times h(i) \\ f(a) + f(b) & < (w(b + 1) - w(a + 1)) \times h(i) \\ f(a) + f(b) \over w(b + 1) - w(a + 1) & < h(i) \\ \end{align*}

维护决策点,使斜率递增,最优决策取队首。时间复杂度为 O(n)

代码

#include <cstdio>
#include <climits>
#include <utility>
#include <functional>
#include <algorithm>
#include <vector>

const int MAXN = 50000;

std::pair<int, int> A[MAXN];
std::vector< std::pair<int, int>* > vec;

int n;
long long f[MAXN + 1];

inline void prepare() {
    std::sort(A, A + n, std::greater< std::pair<int, int> >());

    std::pair<int, int> *last = NULL;
    for (int i = 0; i < n; i++) {
        if (!last || A[i].second > last->second) {
            vec.push_back(&A[i]);
            last = &A[i];
        }
    }

    n = vec.size();
}

inline long long w(const int i) { return static_cast<long long>(vec[i - 1]->first); }
inline long long h(const int i) { return static_cast<long long>(vec[i - 1]->second); }

inline void force() {
    f[0] = 0;
    std::fill(f + 1, f + n + 1, LLONG_MAX);
    for (int i = 1; i <= n; i++) {
        int _j = -1;
        for (int j = 0; j < i; j++) {
            if (f[i] > f[j] + w(j + 1) * h(i)) {
                f[i] = f[j] + w(j + 1) * h(i);
                _j = j;
            }
        }
        // printf("%d --> %d\n", i, _j);
    }
}

inline double slope(const int a, const int b) {
    return double(f[a] - f[b])
         / double(w(b + 1) - w(a + 1));
}

inline void dp() {
    f[0] = 0;
    std::fill(f + 1, f + n + 1, LLONG_MAX);

    static int q[MAXN + 1];
    int *l = &q[0], *r = &q[0];
    *r = 0;

    for (int i = 1; i <= n; i++) {
        while (l < r && slope(*(l + 1), *l) < h(i)) l++;

        int tmp = *l;
        f[i] = f[tmp] + w(tmp + 1) * h(i);
        // printf("%d --> %d\n", i, tmp);

        if (i != n) {
            while (l < r && slope(*r, *(r - 1)) > slope(*r, i)) r--;
            *++r = i;
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d %d", &A[i].first, &A[i].second);

    prepare();
    // for (int i = 0; i < n; i++) printf("%d %d\n", vec[i]->first, vec[i]->second);

    // force();
    dp();
    printf("%lld\n", f[n]);

    return 0;
}