[USACO 2008 MAR] 土地购买

[题目链接]

https://www.lydsy.com/JudgeOnline/problem.php?id=1597

[算法]

首先将所有土地按长为第一关键字 ， 宽为第二关键字排序

显然 ， 当i > j , 且yi >= yj时 ， 土地j没有用 ， 不妨使用单调栈弹出所有没有用的土地

用fi表示前i块土地的最小经费

显然 ， fi = min{ fj + aibj }

斜率优化即可

时间复杂度 : O(N)

[代码]

#include<bits/stdc++.h>

using namespace std;

#define N 50010

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

const ll inf = 1e18;

struct info

{

        ll x , y;

} a[N];

ll n , l , r , top;

ll f[N];

ll q[N] , X[N] , Y[N] , s[N];

template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); }

template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); }

template <typename T> inline void read(T &x)

{

    T f = ; x = ;

    char c = getchar();

    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;

    for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

    x *= f;

}

inline bool cmp(info a , info b)

{

        if (a.x != b.x) return a.x < b.x;

        else return a.y < b.y;

}

int main()

{

        read(n);

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

        {

                read(a[i].x);

                read(a[i].y);

        }

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

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

        {

                while (top >  && a[i].y >= a[s[top]].y) --top;

                s[++top] = i;

        }

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

                X[i] = -a[s[i + ]].y;

        q[f[l = r = ] = ] = ;

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

        {

                while (l < r && Y[q[l + ]] - Y[q[l]] <= a[s[i]].x * (X[q[l + ]] - X[q[l]])) ++l;

                f[i] = f[q[l]] - a[s[i]].x * X[q[l]];

                Y[i] = f[i];

                while (l < r && (Y[i] - Y[q[r]]) * (X[q[r]] - X[q[r - ]]) <= (Y[q[r]] - Y[q[r - ]]) * (X[i] - X[q[r]])) --r;

                q[++r] = i;

        }

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

        return ;

}