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

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

链接

BZOJ 1597

题解

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

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

斜率优化，考虑两个决策 、，若 比 优，则有

维护决策点，使斜率递增，最优决策取队首。时间复杂度为 。

代码

#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;
}