首页 > 其他 > 详细

bzoj1537

时间:2017-08-23 00:23:34      阅读:332      评论:0      收藏:0      [点我收藏+]

dp+树状数组

一维排序,一维离散化,然后跑lis,其实就是一个二维偏序

技术分享
#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
int dp[N], tree[N];
struct data {
    int x, y, p;
    inline bool friend operator < (data A, data B)
    {
        return A.x == B.x ? A.y < B.y : A.x < B.x;
    }
} a[N];
int n, m, k, ans;
inline int lowbit(int i)
{
    return i & (-i);
}
inline void update(int pos, int delta)
{
    for(int i = pos; i <= m; i += lowbit(i)) tree[i] = max(tree[i], delta);
}
inline int query(int pos)
{
    int ret = 0;
    for(int i = pos; i; i -= lowbit(i)) ret = max(ret, tree[i]);
    return ret;
} 
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    vector<int> vt;
    for(int i = 1; i <= k; ++i) 
    {
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].p);
        vt.push_back(a[i].y);
    }
    sort(vt.begin(), vt.end());
    vt.erase(unique(vt.begin(), vt.end()), vt.end());
    for(int i = 1; i <= k; ++i) a[i].y = lower_bound(vt.begin(), vt.end(), a[i].y) - vt.begin() + 1;
    m = vt.size() + 10;
    sort(a + 1, a + k + 1);
    for(int i = 1; i <= k; ++i)
    {
        dp[i] = query(a[i].y) + a[i].p;
        ans = max(ans, dp[i]);
        update(a[i].y, dp[i]);
    }
    printf("%d\n", ans);
    return 0;
}
View Code

 

bzoj1537

原文:http://www.cnblogs.com/19992147orz/p/7414101.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!