「BZOJ1537」[POI2005] Aut – The Bus
Description
Byte City 的街道形成了一个标准的棋盘网络 – 他们要么是北南走向要么就是西东走向. 北南走向的路口从 1 到 n编号, 西东走向的路从1 到 m编号. 每个路口用两个数(i, j) 表示(1 <= i <= n, 1 <= j <= m). Byte City里有一条公交线, 在某一些路口设置了公交站点. 公交车从 (1, 1) 发车, 在(n, m)结束.公交车只能往北或往东走. 现在有一些乘客在某些站点等车. 公交车司机希望在路线中能接到尽量多的乘客.帮他想想怎么才能接到最多的乘客.
Input
第一行三个数n, m 和 k – 表示北南走向的路的个数以及西东走向的路和乘客等车的站点的个数. ( 1 <= n <= 10^9, 1 <= m <= 10^9, 1 <= k <= 10^5). 接下来k 行每行描述一个公交站的信息.第 i + 1 行三个正整数 xi, yi 和 pi, 1 <= xi <= n, 1 <= yi <= m, 1 <= pi <= 10^6. 表示在(xi, yi) 有 pi 个乘客在等车. 每个路口在数据中最多出现一次,乘客总数不会超过1 000 000 000.
Output
一个数表示最多能接到的乘客数量.
Sample Input
8 7 11
4 3 4
6 2 4
2 3 2
5 6 1
2 5 2
1 5 5
2 1 1
3 1 1
7 7 1
7 4 2
8 6 2
4 3 4
6 2 4
2 3 2
5 6 1
2 5 2
1 5 5
2 1 1
3 1 1
7 7 1
7 4 2
8 6 2
Sample Output
11
题解
对于y坐标离散化
然后按照x坐标排序
f[i]=max(f[j]+p[i])(y[j]<y[i],j<i)，最大值我们可以搞个树状数组
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int n,ans; int t[100005],hash[100005]; struct data{int x,y,p;}a[100005]; inline bool cmp(data a,data b) {if(a.x==b.x)return a.y<b.y;return a.x<b.x;} int find(int x) { int l=1,r=n; while(l<=r) { int mid=(l+r)>>1; if(hash[mid]<x)l=mid+1; else if(hash[mid]==x)return mid; else r=mid-1; } } inline int lowbit(int x){return x&(-x);} void change(int x,int val) { for(int i=x;i<=n;i+=lowbit(i)) t[i]=max(val,t[i]); } int ask(int x) { int tmp=0; for(int i=x;i>0;i-=lowbit(i)) tmp=max(tmp,t[i]); return tmp; } int main() { n=read(),n=read(),n=read(); for(int i=1;i<=n;i++) { a[i].x=read();a[i].y=read();a[i].p=read(); hash[i]=a[i].y; } sort(hash+1,hash+n+1); sort(a+1,a+n+1,cmp); int tmp,pos; for(int i=1;i<=n;i++) { pos=find(a[i].y); tmp=a[i].p+ask(pos); change(pos,tmp); ans=max(ans,tmp); } printf("%d",ans); return 0; } |
Subscribe
计数器 9787305
OI 课件=>
OI 课件=>