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

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

[POI2005]AUT-The Bus

## 代码

```#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;
}﻿​```

209 人读过

0 条评论