洛谷2900 [USACO08MAR]Land Acquisition

题意

有 $N$ 块矩形土地，面积为 $W_i\times H_i$ 。可以购买单个土地，价格为面积；也可以将多个土地合并起来买，价格为 $\max W\times \max H$ 。要将所有土地买下来，求最小花费。

$N\le 50000$ 。

题解

对于两块土地 $i,j$ ，如果 $H_i\le H_j,W_i\le W_j$ ，那么买 $j$ 的时候顺便把 $i$ 带上就行了，$i$ 就可以删去。

具体的操作为先按 $H$ 从小到大排序，然后依次入栈，入栈前从栈顶依次把 $W_{top}\le W_i$ 的土地弹出，最后剩下的土地就是有用的。

可以发现剩下的土地都是按 $H$ 从大到小，$W$ 从小到大排序的。合并起来买的土地一定是连续的，因为合并买 $i,j$ ，与买 $[i,j]$ 的价格都是 $H_i\times W_j$ 。

用 $f[i]$ 表示前 $i$ 块土地的最小花费，方程式为：

$$f[i]=\min f[j]+H_{j+1}\times W_i$$

$$f[j]=-W_i\times H_{j+1}+f[i]$$

可以斜率优化，斜率 $-W_i$ 单调。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

struct node {
    ll x,y;
} s[50005];
stack <ll> t;
ll n,f[50005],h[50005],w[50005],q[50005];

inline double slope(int x,int y) { return -1.0*(f[y]-f[x])/(h[y+1]-h[x+1]); }

signed main()
{
    n=read();
    for (ll i=1;i<=n;i++) s[i].x=read(),s[i].y=read();
    sort(s+1,s+n+1,[](const node &x,const node &y){ return x.x==y.x ? x.y<y.y : x.x<y.x; });
    for (ll i=1;i<=n;i++)
    {
        while (!t.empty() && s[t.top()].y<=s[i].y) t.pop();
        t.emplace(i);
    }
    ll cnt=0;
    for (;!t.empty();t.pop()) h[++cnt]=s[t.top()].x,w[cnt]=s[t.top()].y;
    n=cnt;
    ll l=1,r=1; q[1]=0;
    for (ll i=1;i<=n;i++)
    {
        while (l<r && slope(q[l],q[l+1])<=w[i]) l++;
        f[i]=f[q[l]]+h[q[l]+1]*w[i];
        while (l<r && slope(q[r-1],q[r])>=slope(q[r],i)) r--;
        q[++r]=i;
    }
    return !printf("%lld",f[n]);
}