题目

洛谷 P3431 [POI2005]AUT-The Bus

Description

某城市的街道形成了一个棋盘网络.他们要么是北南走向要么就是西东走向.北南走向的路口从 \(1\) 到 \(n\) 编号,西东走向的路从 \(1\) 到 \(m\) 编号.每个路口用两个数\((i,j)\)表示\((1\le i\le n,1\le j\le m)\).

该城市里有一条公交线,在某一些路口设置了公交站点.公交车从$ (1, 1) \(发车,在\)(n, m)$结束.公交车只能往北或往东走.现在有一些乘客在某些站点等车.公交车司机希望在路线中能接到尽量多的乘客.帮他想想怎么才能接到最多的乘客.

Input

第一行三个数 \(n, m\) 和 \(k\) 表示北南走向的路的个数以及西东走向的路和乘客等车的站点的个数.$ ( 1 \le n \le 10^9, 1 \le m \le 10^9, 1 \le k \le 10^5)$.

接下来 \(k\) 行每行描述一个公交站的信息.第 \(i + 1\) 行三个正整数 \(x_i,y_i\) 和 \(p_i\), \(1\le x_i \le n, 1 \le y_i \le m, 1 \le p_i \le 10^6\).表示在\((x_i,y_i)\)有 \(p_i\) 个乘客在等车.每个路口在数据中最多出现一次,乘客总数不会超过\(1 000 000 000\).

Output

一个数,表示最多能接到的乘客数量.

Sample Input 1

8 7 11
4 3 4
6 2 4
2 3 2
5 6 1
2 5 2
1 5 5
2 1 1
3 1 1
7 7 1
7 4 2
8 6 2

Sample Output 1

11

思路

动态规划.

首先把所有公交站的横纵坐标离散化到\([1,n]\)的范围内,容易发现不影响答案.

然后把车站以横坐标为第一关键字,纵坐标为第二关键字排序,从前到后扫描所有车站,那么如果一个车站\(i\)的纵坐标比它前面的某个车站\(j\)的纵坐标大,那么一定可以从\(j\)转移到\(i\).这样做的时间复杂度是\(O(n^2)\)的.

那么可以考虑设\(DP[i]\)表示纵坐标为\(i\)时能取得的最大乘客数量.

如果现在枚举到车站\(j\),有:

\(DP[y_j]=\max(DP[1...y_j])+p_j\).

于是用一颗支持单点修改,区间查询最小值的线段树维护\(DP[]\)数组即可.

正确性显然,时间复杂度\(O(nlogn)\).

道理我都懂,可是线段树空间要开4倍??

讲评时,教练提到也可以用树状数组维护前缀最大值.

#include<bits/stdc++.h>
const int SIZE=200005;

int n,m,k,Tem[SIZE],Tot,DP[SIZE],Ans;
struct Stop
{
    int X,Y,P;
    bool operator <(const Stop &o)const
    {
        if(X!=o.X)return X<o.X;
        return Y<o.Y;
    }
}A[SIZE];

struct Seg_Tree
{
    int Max[SIZE*4];
    #define LC(x) (x<<1)
    #define RC(x) (x<<1|1)
    #define Mid ((L+R)>>1)
    void push_up(int x){Max[x]=std::max(Max[LC(x)],Max[RC(x)]);}
    void Change(int p,int L,int R,int X,int K)
    {
        if(L==R){Max[p]=K;return;}
        if(X<=Mid)Change(LC(p),L,Mid,X,K);
        else Change(RC(p),Mid+1,R,X,K);
        push_up(p);
    }
    int Query_max(int p,int L,int R,int X,int Y)
    {
        if(L>Y||R<X)return 0;
        if(L>=X&&R<=Y)return Max[p];
        return std::max(Query_max(LC(p),L,Mid,X,Y),Query_max(RC(p),Mid+1,R,X,Y));
    }
}T;

int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;i++)
    {
        scanf("%d%d%d",&A[i].X,&A[i].Y,&A[i].P);
        Tem[++Tot]=A[i].X;
        Tem[++Tot]=A[i].Y;
    }
    std::sort(Tem+1,Tem+1+Tot);
    for(int i=1;i<=k;i++)
    {
        A[i].X=std::lower_bound(Tem+1,Tem+1+Tot,A[i].X)-Tem;
        A[i].Y=std::lower_bound(Tem+1,Tem+1+Tot,A[i].Y)-Tem;
    }
    std::sort(A+1,A+1+k);
    for(int i=1;i<=k;i++)
    {
        if(A[i].Y==1)DP[A[i].Y]=std::max(DP[A[i].Y],A[i].P);
        else DP[A[i].Y]=std::max(DP[A[i].Y],T.Query_max(1,1,Tot,1,A[i].Y-1))+A[i].P;
        T.Change(1,1,Tot,A[i].Y,DP[A[i].Y]);
        Ans=std::max(Ans,DP[A[i].Y]);
    }
    printf("%d",Ans);
    return 0;
}

[POI2005]AUT-The Bus

原文：https://www.cnblogs.com/TaylorSwift13/p/11774936.html