题解 P5244 【[USACO19FEB]Mowing Mischief P】

· · 题解

P5244 题解

宣传博客

题意

二维坐标系中，选择坐标严格递增的一些点，相邻点依次作为对角线组成的长方形面积和最小。

x_0<x_1<...<x_k y_0<y_1<...<y_k

这个应该很容易理解

解答

二维最长不下降序列？
按x排序，一维LIS

假设$p$的最长上升序列长度为$i$，枚举点$p$左下角的所有最长上升序列长度为$i-1$的点$q

那么我们可以写出转移方程：

dp_p=\min_{q∈L_{i-1}\ |\ p>>q}\{dp_q+(x_p-x_q)(y_p-y_q)\}

其中p>>q表示p在q的左上方，L_x表示以x结尾的LIS长度。

那么我们按层dp
一共有S层
对于L_i里的所有点
决策：要在L_{i-1}里选一个点，选哪个？
约束：这个点要在左下方

简化问题：
没有约束？
对于点p_1,p_2∈L_i，q_1,q_2∈L_{i-1}，

X_{p_1}<X_{p_2} -> Y_{p_1}>Y_{p_2} X_{q_1}<X_{q_2} -> Y_{q_1}>Y_{q_2}

可以证明： 如果p_1选择了q_1，那么p_2一定选择q_1

但是这样肯定不能AKIOI，于是我们要优化。
这里就会用到一个常见的手段：\color{red}{决策单调性！}

有约束，怎么办？中国山东找蓝翔
我们发现约束也是连续的！
因此当我们求区间最优解的时候，可以用Segment\ tree来维护。
线段树每个结点表示L_{i-1}的一段区间。

所以我们确定步骤：

  1. 对于第i层的一个点，找到L_{i-1}线段树上所有包含的区间，这些结点上记录下能对该点进行转移。
  2. 每个结点上记录了一些L_i的转移目标，这些转移目标符合单调性。
  3. 遍历L_{i-1}这棵线段树的所有（可转移的）结点，更新L_i的DP值。

代码军

此处借鉴了dalao\text{\color{red}LIdox1536513344}的代码
线段树建树

inline void buildSegTr(int &rt,int l,int r){
  rt=++size;
  a[rt].ls=a[rt].rs=0;
  a[rt].trans.clear();
  if(l==r)return;
  int mid=(l+r)>>1;
  buildSegTr(a[rt].ls,l,mid);
  buildSegTr(a[rt].rs,mid+1,r);
}

转移

inline void Modify(int rt,int l,int r,int x){
    if(p[x].x>=p[point[r]].x&&p[x].y>=p[point[l]].y){
        a[rt].trans.push_back(x);
        return;
    }
    if(p[x].x<=p[point[l]].x||p[x].y<=p[point[r]].y) return;
    int mid=(l+r)>>1;
    Modify(a[rt].ls,l,mid,x);
    Modify(a[rt].rs,mid+1,r,x);
}

解决问题

inline void Solve(int l,int r,int ql,int qr){
    ll ans=inf,from=0;
    int mid=(l+r)>>1,now=tmp[mid];
    for(int i=ql;i<=qr;++i){
        int pos=point[i];
        ll res=dp[pos]+1ll*(p[now].x-p[pos].x)*(p[now].y-p[pos].y);
        if(res<ans){
            ans=res;
            from=i;
        }
    }
    dp[now]=min(dp[now],ans);
    if(l<mid) Solve(l,mid-1,from,qr);
    if(mid<r) Solve(mid+1,r,ql,from);
}
inline void Work(int rt,int l,int r){
    if(a[rt].trans.size()){
        tmp=a[rt].trans;
        Solve(0,tmp.size()-1,l,r);
    }
    if(l==r) return;
    int mid=(l+r)>>1;
    Work(a[rt].ls,l,mid);
    Work(a[rt].rs,mid+1,r);
}

主函数怎么用

sort(p+1,p+n+1,cmpx);
for(ll i=1;i<=n;++i){
    ly[i]=Query(p[i].y)+1;
    Modify(p[i].y,ly[i]);
    pos[ly[i]].push_back(i);
    m=max(m,ly[i]);
}
for(ll i=0,now;i<(ll)pos[1].size();++i)now=pos[1][i],f[now]=1ll*p[now].x*p[now].y;
for(ll i=2,now;i<=m;++i){
    ST.init(pos[i-1]);
    for(ll j=0;j<(ll)pos[i].size();++j){
        now=pos[i][j];
        f[now]=INF;
        ST.modify(now);
    }
    ST.work();
}
ll ans=INF;
for(ll i=0;i<(ll)pos[m].size();++i){
    ll now=pos[m][i];
    ans=min(ans,f[now]+1ll*(T-p[now].x)*(T-p[now].y));
}

最后放一次完整代码（有修改）

#include<bits/stdc++.h>
#define SIZE_N 300005
#define SIZE_T 1000005
#define INF 2e18
using namespace std;
typedef long long ll;
namespace Mischief{
    struct Node{ll x,y;}p[SIZE_N];
    inline bool cmpx(Node a,Node b){return a.x==b.x?a.y<b.y:a.x<b.x;}
    ll T,n,m,s,ly[SIZE_N],f[SIZE_N],bit[SIZE_T];
    vector<ll> pos[SIZE_N];
    inline ll LSB(ll x){return x&(-x);}
    inline void Modify(ll x,ll v){for(ll i=x;i<=T;i+=LSB(i))bit[i]=max(bit[i],v);}
    inline ll Query(ll x){ll res=0;for(ll i=x;i;i-=LSB(i))res=max(res,bit[i]);return res;}
    struct Segment_Tree{
        struct Node{
            ll ls,rs;
            vector<ll> trans;
        }a[SIZE_N<<1];
        ll n,size,rt;
        vector<ll> poll,tmp;
        inline void buildSt(ll &rt,ll l,ll r){
            rt=++size;
            a[rt].ls=a[rt].rs=0;
            a[rt].trans.clear();
            if(l==r)return;
            ll mid=(l+r)>>1;
            buildSt(a[rt].ls,l,mid);
            buildSt(a[rt].rs,mid+1,r);
        }
        inline void init(vector<ll> tmp){
            poll=tmp;
            n=tmp.size();
            rt=size=0;
            buildSt(rt,0,n-1);
        }
        inline void Modify(ll rt,ll l,ll r,ll x){
            if(p[x].x>=p[poll[r]].x&&p[x].y>=p[poll[l]].y){
                a[rt].trans.push_back(x);
                return;
            }
            if(p[x].x<=p[poll[l]].x||p[x].y<=p[poll[r]].y)return;
            ll mid=(l+r)>>1;
            Modify(a[rt].ls,l,mid,x);
            Modify(a[rt].rs,mid+1,r,x);
        }
        inline void modify(ll x){Modify(rt,0,n-1,x);}
        inline void Solve(ll l,ll r,ll ql,ll qr){
            ll ans=INF,from=0;
            ll mid=(l+r)>>1,now=tmp[mid];
            for(ll i=ql;i<=qr;++i){
                ll pos=poll[i];
                ll res=f[pos]+1ll*(p[now].x-p[pos].x)*(p[now].y-p[pos].y);
                if(res<ans)ans=res,from=i;
            }
            f[now]=min(f[now],ans);
            if(l<mid)Solve(l,mid-1,from,qr);
            if(mid<r)Solve(mid+1,r,ql,from);
        }
        inline void Work(ll rt,ll l,ll r){
            if(a[rt].trans.size())tmp=a[rt].trans,Solve(0,tmp.size()-1,l,r);
            if(l==r)return;
            ll mid=(l+r)>>1;
            Work(a[rt].ls,l,mid);
            Work(a[rt].rs,mid+1,r);
        }
        inline void work(){Work(rt,0,n-1);}
    }ST;
    inline int _main(){
        scanf("%lld%lld",&n,&T);
        for(ll i=1;i<=n;++i)scanf("%lld%lld",&p[i].x,&p[i].y);
        sort(p+1,p+n+1,cmpx);
        for(ll i=1;i<=n;++i){
            ly[i]=Query(p[i].y)+1;
            Modify(p[i].y,ly[i]);
            pos[ly[i]].push_back(i);
            m=max(m,ly[i]);
        }
        for(ll i=0,now;i<(ll)pos[1].size();++i)now=pos[1][i],f[now]=1ll*p[now].x*p[now].y;
        for(ll i=2,now;i<=m;++i){
            ST.init(pos[i-1]);
            for(ll j=0;j<(ll)pos[i].size();++j){
                now=pos[i][j];
                f[now]=INF;
                ST.modify(now);
            }
            ST.work();
        }
        ll ans=INF;
        for(ll i=0;i<(ll)pos[m].size();++i){
            ll now=pos[m][i];
            ans=min(ans,f[now]+1ll*(T-p[now].x)*(T-p[now].y));
        }
    }
}using namespace Mischief;
int main(){
    _main();
    return 0;
}

什么你不想翻上去点赞？那就点这里吧！