Luogu 2900 [USACO08MAR]土地征用Land Acquisition

斜率优化dp。

首先发现如果存在$x$和$y$使得$len(x) \geq len(y)$并且$wid(x) \geq wid(y)$，那么$y$直接不考虑就好了，因为在买$x$的时候就把$y$顺便带上了。

随便按照$x$或者$y$排一波序就能很方便地处理了。

接下来就可以设计dp了，设去重之后有$tot$个元素，$f_{i}$表示$1~i$地代价的最小值。

如果按照$len$从大到小排序，此时在排完序的序列中一定也满足$wid$不递增。

有转移方程：$f_{i} = min(f_{j} + len(i) * wid(j + 1))$    $(0 \leq j < i)$。

发现了$len(i) * wid(j + 1)$的项，得到斜率式为$(f_{j} - f_{k}) / (wid(k + 1) - wid(j + 1)) <= len(i)$   $(k < j)$。

然后按照套路写一个单调队列就好了。

时间复杂度$O(nlogn)$。

Code：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

typedef double db;

const int N = 5e4 + ;

int n, tot = , q[N];

ll f[N];

struct Item {

    ll len, wid;

} a[N], b[N];

bool cmp(const Item &x, const Item &y) {

    if(x.len == y.len) return x.wid < y.wid;

    else return x.len < y.len;

}

template <typename T>

inline void read(T &X) {

    X = ; char ch = ; T op = ;

    for(; ch > '' || ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

inline db slope(int i, int j) {

    return (db)(f[i] - f[j]) * 1.0 / (b[j + ].wid - b[i + ].wid);

}

int main() {

//    freopen("testdata.txt", "r", stdin);

    read(n);

    for(int i = ; i <= n; i++)

        read(a[i].len), read(a[i].wid);

    sort(a + , a +  + n, cmp);

    for(int i = ; i <= n; i++) {

        for(; tot >  && a[i].wid >= b[tot].wid; --tot);

        b[++tot] = a[i];

    }

/*    printf("\n");

    for(int i = 1; i <= tot; i++)

        printf("%lld %lld\n", b[i].len, b[i].wid);    */

//    memset(f, 0x3f, sizeof(f)); f[0] = 0LL;

    int l = , r = ; q[] = ;

    for(int i = ; i <= tot; i++) {

        for(; l < r && slope(q[l], q[l + ]) <= (db)b[i].len; ++l);

        f[i] = f[q[l]] + 1LL * b[i].len * b[q[l] + ].wid;

        for(; l < r && slope(q[r - ], q[r]) >= slope(q[r], i); --r);

        q[++r] = i;

    }

/*    for(int i = 1; i <= tot; i++)

        printf("%lld ", f[i]);

    printf("\n");   */

    printf("%lld\n", f[tot]);

    return ;

}