P2900 [USACO08MAR] Land Acquisition G 题解

· · 题解

不明白为啥没人写李超线段树。

斜率优化的题通常李超也能做，这题 n 不大，长宽的值域也很小，所以完全可以李超。

状态转移方程是咋来的请看别的题解。

f_i=f_j +H_iW_{j+1}

其中 H 是长，W 是宽，我的排序方式和别人不太一样，可以看看我代码理解一下，这不是重点。

那么我们设 K_j=W_{j+1},B_j=f_j，那么每个位置都可以当做一个函数 F_j(x)，然后我们发现：

f_i=\min_{j<i}F_j(H_i)

所以我们就用李超维护这些直线，求最小值就很简单了。

时间复杂度是 \mathcal O(n\log n) 的。

#include<bits/stdc++.h>
#define LL long long
#define LF double
#define pLL pair<LL,LL>
#define pb push_back
//#define Fi first
//#define Se second
#define Ls(x) (x<<1)
#define Rs(x) (x<<1|1)
//#define Ls(x) t[x].Lson
//#define Rs(x) t[x].Rson
using namespace std;
const LL Inf=1e18;
const LL N=1e6+5;
const LL M=1e6;
//const LL Mod;
//const LF eps;
//const LL P;
struct Nd
{
    LL H,W;
}A[N],B[N];
LL n,tot,F[N];
struct Line
{
    LL k,b;
}L[N];
LL Cal(LL i,LL x)
{
    return L[i].k*x+L[i].b;
}
bool Pd(LL i,LL j,LL x)
{
    return Cal(i,x)<Cal(j,x);
}
LL Mn[N<<2];
void Upd(LL rt,LL l,LL r,LL x)
{
    if(l==r)
    {
        if(Pd(x,Mn[rt],l))Mn[rt]=x;
        return;
    }
    LL mid=l+r>>1;
    if(Pd(x,Mn[rt],mid))swap(x,Mn[rt]);
    if(Pd(x,Mn[rt],l))Upd(Ls(rt),l,mid,x);
    if(Pd(x,Mn[rt],r))Upd(Rs(rt),mid+1,r,x);
}
LL Qry(LL rt,LL l,LL r,LL x)
{
    LL t=Cal(Mn[rt],x);
    if(l==r)return t;
    LL mid=l+r>>1;
    if(x<=mid)return min(t,Qry(Ls(rt),l,mid,x));
    return min(t,Qry(Rs(rt),mid+1,r,x));
}
void Ins(LL x)
{
    L[x]={B[x+1].W,F[x]};
    Upd(1,1,M,x);
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&A[i].H,&A[i].W);
    }
    sort(A+1,A+n+1,[](Nd x,Nd y)
        {
            if(x.H!=y.H)return x.H<y.H;
            return x.W<y.W;
        });
    for(int i=n;i>=1;i--)
    {
        if(A[i].W>=B[tot].W)B[++tot]=A[i];
    }
    n=tot;
    sort(B+1,B+n+1,[](Nd x,Nd y)
        {
            if(x.H!=y.H)return x.H<y.H;
            return x.W<y.W;
        });
    L[0]={0,Inf};
    L[n+1]={B[1].W,0};
    Upd(1,1,M,n+1);
    F[1]=B[1].W*B[1].H;
    Ins(1);
    for(int i=2;i<=n;i++)
    {
        F[i]=Qry(1,1,M,B[i].H);
    //  cout<<B[i].H<<' '<<B[i].W<<' '<<F[i]<<endl;
        Ins(i);
    }
    printf("%lld\n",F[n]);
    return 0;
}
//RP++