[BZOJ1537/Luogu3431][POI2005]AUT-The Bus

题目链接：

BZOJ1537.

Luogu3431

首先离散化一波，然后以\(x\)为第一关键字，\(y\)为第二关键字排序。

从前往后扫，设\(f[i]\)表示到达\(i\)站的最多乘客，很容易有转移方程\(f[i]=max(f[j])+p[i]\)，其中\((j\le i),y[j]\le y[i]\)

那么就可以用线段树优化。

时间复杂度 \(O(nlog_2n)\)

代码：

#include <cstdio>
#include <algorithm>

int n,Ans,b[100005],bl;
struct Station
{
    int x,y,p;
    inline bool operator<(const Station &o)const
    {return x==o.x?y<o.y:x<o.x;}
}s[100005];
struct Segment_Tree
{
    int a[400005];
    
    inline void Modify(const int p,const int l,const int r,const int o,const int v)
    {
        if(l==r){a[p]=v;return;}
        const int Mid=(l+r)>>1;
        if(o<=Mid)Modify(p<<1,l,Mid,o,v);
        else Modify(p<<1|1,Mid+1,r,o,v);
        a[p]=std::max(a[p],v);
    }
    
    inline int Query(const int p,const int l,const int r,const int tl,const int tr)
    {
        if(tl<=l&&r<=tr)return a[p];
        int Mid=(l+r)>>1,Res=0;
        if(tl<=Mid)Res=Query(p<<1,l,Mid,tl,tr);
        if(tr>Mid)Res=std::max(Res,Query(p<<1|1,Mid+1,r,tl,tr));
        return Res;
    }
}ST;

int main()
{
    scanf("%*d%*d%d",&n);//Input(n,m are useless)
    for(int i=1;i<=n;++i)scanf("%d%d%d",&s[i].x,&s[i].y,&s[i].p);
    
    for(int i=1;i<=n;++i)b[i]=s[i].x;
    std::sort(b+1,b+n+1),bl=std::unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i)s[i].x=std::lower_bound(b+1,b+bl+1,s[i].x)-b;
    
    for(int i=1;i<=n;++i)b[i]=s[i].y;
    std::sort(b+1,b+n+1),bl=std::unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i)s[i].y=std::lower_bound(b+1,b+bl+1,s[i].y)-b;
    
    std::sort(s+1,s+n+1);
    for(int i=1;i<=n;++i)ST.Modify(1,1,n,s[i].y,ST.Query(1,1,n,1,s[i].y)+s[i].p);
    printf("%d\n",ST.Query(1,1,n,1,n));
    return 0;
}

[BZOJ1537/Luogu3431][POI2005]AUT-The Bus

原文：https://www.cnblogs.com/LanrTabe/p/10452637.html