icontofig | 发布于 2019-02-27 23:53:01 | 阅读量 209 | 树状数组
发布于 2019-02-27 23:53:01 | 树状数组

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

[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;
}​

内容更新于: 2019-02-27 23:53:01
链接地址: http://blog.leanote.com/post/icontofig/BZOJ-1537-POI2005-AUT

上一篇: CCF-CSP201812-2小明放学

下一篇: HDU-5441 Travel 贪心+加权并查集

209 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航