题目描述

Description

Byte City 的街道形成了一个标准的棋盘网络 – 他们要么是北南走向要么就是西东走向. 北南走向的路口从 1 到 n编号, 西东走向的路从1 到 m编号. 每个路口用两个数(i, j) 表示(1 <= i <= n, 1 <= j <= m). Byte City里有一条公交线, 在某一些路口设置了公交站点. 公交车从 (1, 1) 发车, 在(n, m)结束.公交车只能往北或往东走. 现在有一些乘客在某些站点等车. 公交车司机希望在路线中能接到尽量多的乘客.帮他想想怎么才能接到最多的乘客.

Input

第一行三个数n, m 和 k – 表示北南走向的路的个数以及西东走向的路和乘客等车的站点的个数. ( 1 <= n <= 10^9, 1 <= m <= 10^9, 1 <= k <= 10^5). 接下来k 行每行描述一个公交站的信息.第 i + 1 行三个正整数 xi, yi 和 pi, 1 <= xi <= n, 1 <= yi <= m, 1 <= pi <= 10^6. 表示在(xi, yi) 有 pi 个乘客在等车. 每个路口在数据中最多出现一次,乘客总数不会超过1 000 000 000.

Output

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

Sample Input

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

11

题目分析

将坐标离散化 二维偏序的话一维排序 一维树状数组维护个数

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
long long f[200000];
struct your
{
    int x,y,c;
}a[100010];
long long dp[100010];
int cmp(your j,your k)
{
    return j.y<k.y;
}
int cmp2(your j,your k)
{
    if(j.x==k.x) return j.y<k.y;
    return j.x<k.x;
}
int tot;
int y[100010];
int __,___;
void update(int x,long long c)
{
    for(;x<=tot;x+=x&-x) f[x]=max(f[x],c);
}
long long ask(int x)
{
    long long sum=0;
    for(;x;x-=x&-x) sum=max(sum,f[x]);
    return sum;
}   
int main()
{
    scanf("%d%d%d",&__,&___,&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(a[i].y!=a[i-1].y) tot++;
        y[i]=tot;
    }
    for(int i=1;i<=n;i++) a[i].y=y[i];
    sort(a+1,a+n+1,cmp2);
    long long ans=0;  
    for(int i=1;i<=n;i++)
    {
        dp[i]=(long long) a[i].c+ask(a[i].y);
        update(a[i].y,dp[i]);
        ans=max(ans,dp[i]);
    }
    printf("%lld",ans);
    return 0;   
}