2019 ICPC Asia Xuzhou Regional K K-rectangle【ICPC徐州J】【DP】【斜率优化】【可回退化凸包】

87 阅读 0 评论 58 点赞

我是靠谱客的博主拼搏季节，最近开发中收集的这篇文章主要介绍2019 ICPC Asia Xuzhou Regional K K-rectangle【ICPC徐州J】【DP】【斜率优化】【可回退化凸包】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目大意

平面上有 $n$ 个点，求用若干个底落在 $x$ 轴的矩形来覆盖所有点，并且使得代价最小.
其中一个 $w \cdot h$ 矩形的代价为 $(w + k) \cdot h$ ， $k$ 为大于 $0$ 的常数。
$10^5，kle 10^6$

题解

这种题最容易想到的就是 $d p$ ， $d p [i]$ 表示覆盖前 $i$ 个点的最小代价，那么转移显然有: $d p [i] = d p [j - 1] + m a x {h [j], h [j + 1], . . h [i]} \cdot (x [i] - x [j] + k)$
暴力转移的复杂度显然是不对的，考虑怎么优化。
如果使用单调栈去维护以 $i$ 结尾的最大值相同的连续段，那么容易知道总的连续段个数是 $O (n)$ 的，而在同一个连续段中 $m a x$ 是固定的，则有： $d p [i] = d p [j - 1] + m a x \cdot (x [i] - x [j] + k)$ 即： $d p [i] = m a x \cdot x [i] + {d p [j - 1] + m a x \cdot (k - x [j])} = m a x \cdot x [i] + f (m a x)$
而在一个连续段中， $f (m a x) = d p [j - 1] + m a x \cdot (k - x [j])$ 是一个斜率优化的形式，线段树维护凸包即可查询同一连续段中 $m a x$ 对应的最优的 $j$ .

那么现在的问题就是在单调栈后插入/删除若干个连续段，要支持查询 $m a x \cdot x [i] + f (m a x)$ 的最小值。这也是一个斜率优化的形式，所以肯定是凸包无疑了，而由于只会在最后面加入/删除，所以凸包只要支持可回退化即可（注意在凸包加点的时候要二分来加点）

即该题只需要维护两个凸包即可，复杂度 $O (n lo g n)$ （注意在线段树上查询最值的时候不要二分，由于每次查询的 $x [i]$ 是单调的，利用决策单调性维护一个指针扫过去即可）.

#include<bits/stdc++.h>
#define maxh 20
#define maxn 400050
using namespace std;
typedef long long LL;

const int lim=1e6;
const LL inf=1LL<<60;

int n,m;

struct node {
    LL x,y;
    node(LL _x=0,LL _y=0)   {
        x=_x,y=_y;
    }
    node operator - (const node& N) const   {
        return node(x-N.x,y-N.y);
    }
    LL operator * (const node& N) const {
        return x*N.y-y*N.x;
    }
    LL operator ()(const LL& k) const   {
        return k*x-y;
    }
} P[maxn];

ostream& operator << (ostream& os,const node& N)    {
    os<<"("<<N.x<<","<<N.y<<")";
    return os;
}

namespace SegT  {
    const int M=524288;

    int pointer[M<<1];
    vector<node> T[M<<1];
    
    void insert(int i,node p)   {
        p.y=-p.y;
        T[i+M-1].push_back(p);
        for (int k=i+M-1,len=1;k>1&&(k&1);)   {
            k>>=1,len<<=1;
            for (int j=i-len+1;j<=i;++j)  {
                node p=T[j+M-1].back();
                while (T[k].size()>1&&(T[k].back()-p)*(T[k][T[k].size()-2]-p)>=0)  T[k].pop_back();
                T[k].push_back(p);
            }
        }
    }

    LL query(int rt,LL k) {
        int &ptr=pointer[rt];
        while (ptr+1<T[rt].size()&&T[rt][ptr](k)>T[rt][ptr+1](k))    ++ptr;
        return T[rt][ptr](k);
    }

    LL query(int rt,int l,int r,int a,int b,LL k) {
        if (a>r||l>b)   return inf;
        if (a<=l&&r<=b) return query(rt,k);
        int mid=(l+r)>>1;
        return min(query(rt<<1,l,mid,a,b,k),query(rt<<1|1,mid+1,r,a,b,k));
    }

    LL query(int l,int r,LL k)  {   return query(1,1,M,l,r,k);  }
}

namespace DCH   {
    int n;
    node P[maxn];

    pair<int,int> backup[maxn];
    int stk[maxn],tp;

    void pushback(node p) {
        p.y=-p.y;
        P[++n]=p;

        int l=1,r=tp;
        while (l<r) {
            int mid=(l+r+1)>>1;
            if ((P[stk[mid]]-p)*(P[stk[mid-1]]-p)<0)
                l=mid;
            else
                r=mid-1;
        }

        backup[n]=make_pair(stk[r+1],tp);
        stk[tp=r+1]=n;
    }

    void rollback() {
        assert(n);
        stk[tp]=backup[n].first;
        tp=backup[n].second;
        --n;
    }

    LL query(LL k)  {
        int l=1,r=tp;
        while (l<r) {
            int mid=(l+r)>>1;
            if (P[stk[mid]](k)>P[stk[mid+1]](k))
                l=mid+1;
            else
                r=mid;
        }
        return P[stk[l]](k);
    }
}

int stk[maxn],tp;

LL dp[maxn];

int main()  {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i)
        scanf("%lld%lld",&P[i].x,&P[i].y);
    
    for (int i=1;i<=n;++i)  {
        SegT::insert(i,node(m-P[i].x,dp[i-1]));
        for (;tp&&P[stk[tp]].y<=P[i].y;--tp)
            DCH::rollback();
        DCH::pushback(node(P[i].y,SegT::query(stk[tp]+1,i,P[i].y)));
        stk[++tp]=i;
        dp[i]=DCH::query(P[i].x);
    }

    printf("%lldn",dp[n]);
    cerr<<clock()<<endl;
    return 0;
}