BZOJ 1537 POI2005 AUT-The Bus 二维偏序问题

文章来自  Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

由于格式问题,这道题的题面就不往这里放了,给一个洛谷的链接吧:

[POI2005]AUT-The Bus

题解

这道题有中文题意,没有BZOJ权限号的可以去洛谷上搜到这道题。
首先会想到DP,但是一看这个数据范围也太大了,离散化后也没法做二维DP。
但是离散化也是要的,不然10的9次方的数据谁顶得住啊。
考虑这是一个二维偏序问题。一般的二维偏序都是找比当前物品的两个值都小的问题,而这道题并不是,这道题要做的是维护最大前缀和。
首先按照y排序并且离散化每个车站的y坐标,然后再按照x排序,使用树状数组维护最大前缀和即可(当然线段树应该也是可以的,只不过会比树状数组麻烦一点)。注意这里的树状数组不是维护的前缀和,而是维护前缀和的最大值。所以update操作和query操作里并不是求和,而是取最大值。


代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}
const int maxn = 1e5+5;
struct point{
    int x,y,k;
}p[maxn];
bool cmp1(point a,point b){
    return a.y < b.y;
}
bool cmp2(point a,point b){
    if(a.x == b.x)return a.y < b.y;
    return a.x < b.x;
}
int lowbit(int x){
    return x & (-x);
}
int c[maxn];
int n,m,k,cnt;
void update(int x,int d){
    while(x <= cnt){
        c[x] = max(c[x],d);
        x += lowbit(x);
    }
    return;
}
int query(int x){
    int res = 0;
    while(x > 0){
        res = max(res,c[x]);
        x -= lowbit(x);
    }
    return res;
}
int main(){
    n = get_num();
    m = get_num();
    k = get_num();
    for(int i = 1;i <= k;++i){
        p[i].x = get_num();
        p[i].y = get_num();
        p[i].k = get_num();
    }
    sort(p+1,p+k+1,cmp1);
    cnt = 0;
    int now = -1;
    for(int i = 1;i <= k;++i){
        if(now == p[i].y)
            p[i].y = cnt;
        else{
            now = p[i].y;
            p[i].y = ++cnt;
        }
    }
    sort(p+1,p+k+1,cmp2);
    int ans = 0;
    for(int i = 1;i <= k;++i){
        now = query(p[i].y) + p[i].k;
        ans = max(ans,now);
        update(p[i].y,now);
    }
    printf("%d",ans);
    return 0;
}​
Sign in to leave a comment.
No Leanote account ? Sign up now.
0 comments
Title - Artist
0:00