首页 > 其他 > 详细

BZOJ1537: [POI2005]Aut- The Bus

时间:2018-10-12 23:22:00      阅读:28      评论:0      收藏:0      [点我收藏+]

标签:lower   条件   lap   oid   题目   scan   date   ace   highlight   

题目是让求 f[i] = max{f[j]} + v[i]      (x[i] >= x[j] && y[i] >= y[j])

按 x 排序后就是把条件 x[i] >= x[j] 变成了 i > j

这样就比较可做了

离散化 y

从小到大枚举 i ,用数据结构维护 1~y[i] 中的点中 max(f[j])

可以用树状数组因为是维护前缀max并且值不会变小

直接转移就行

方便统计答案就加了一个坐标为 (n, m) 点权为 0


代码:

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cstdio>
using namespace std;
 
const int MAXN = 100005;
 
struct Node{
    int x, y, uy, val;
    bool operator < (const Node& b) const {
        return ((x == b.x) ? (y < b.y) : (x < b.x));
    }
}pt[MAXN];
int n, m, k, sizu;
int uni[MAXN], f[MAXN], bit[MAXN];
 
inline void update(int x, int val) {
    for( ; x <= sizu; x += (x & -x)) bit[x] = max(bit[x], val);
    return;
}
inline int query(int x) {
    register int ret = 0;
    for( ; x > 0; x -= (x & -x)) ret = max(ret, bit[x]);
    return ret;
}
 
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= k; ++i) {
        scanf("%d%d%d", &pt[i].x, &pt[i].y, &pt[i].val);
        uni[i] = pt[i].y;
    }
    ++k;
    pt[k].x = n; pt[k].y = m; pt[k].val = 0;
    uni[k] = m;
    sort(uni + 1, uni + k + 1);
    sizu = unique(uni + 1, uni + k + 1) - uni - 1;
    for(int i = 1; i <= k; ++i) 
        pt[i].uy = lower_bound(uni + 1, uni + sizu + 1, pt[i].y) - uni;
    sort(pt + 1, pt + k + 1);
    for(int i = 1; i <= k; ++i) {
        f[i] = query(pt[i].uy) + pt[i].val;
        update(pt[i].uy, f[i]);
    }
    printf("%d\n", f[k]);
    return 0;
}

  

BZOJ1537: [POI2005]Aut- The Bus

标签:lower   条件   lap   oid   题目   scan   date   ace   highlight   

原文:https://www.cnblogs.com/xcysblog/p/9780413.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号