题面:
Byte City 的街道形成了一个标准的棋盘网络 – 他们要么是北南走向要么就是西东走向. 北南走向的路口从 1 到 n编号, 西东走向的路从1 到 m编号. 每个路口用两个数(i, j) 表示(1 <= i <= n, 1 <= j <= m). Byte City里有一条公交线, 在某一些路口设置了公交站点. 公交车从 (1, 1) 发车, 在(n, m)结束.公交车只能往北或往东走. 现在有一些乘客在某些站点等车. 公交车司机希望在路线中能接到尽量多的乘客.帮他想想怎么才能接到最多的乘客.
这道题是一道比较水的dp,但是想用原来O(nm)的方法的人注意了n,m<=10^9
你空间时间受得了吗?
但是一看k,k<=10^5
应该是一个O(klogk)的算法
1.首先先把x,y全部离散化
2.可以易得直接转移会是o(k^2),所以求最大值得用数据结构优化(我用的线段树) 3.输出转移中的最大值
#include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdio> #include<cmath> #include<queue> #define ll long long using namespace std; const int INF=0x3f3f3f3f,MAXX=200000; int n,m,k; ll bj1[MAXX+5],bj2[MAXX+5]; struct node{ll x,y,num;}a[MAXX+5]; bool cmp(node x,node y){if(x.x==y.x)return x.y<y.y;return x.x<y.x;}//按y坐标排序 struct tree{ int l,r,maxx; inline void st(int a,int b,int c){l=a,r=b,maxx=c;}//封装的赋值 }tree[MAXX*8+5]; void pushup(int k){tree[k].maxx=max(tree[k<<1].maxx,tree[k<<1|1].maxx);} void Build(int k,int l,int r) { tree[k].st(l,r,0); if(l==r)return; int mid=(l+r)>>1; Build(k<<1,l,mid); Build(k<<1|1,mid+1,r); } void add(int k,int x,int v) { if(tree[k].l>x||tree[k].r<x)return; if(x==tree[k].l&&x==tree[k].r){tree[k].maxx=max(tree[k].maxx,v);return;} add(k<<1,x,v); add(k<<1|1,x,v); pushup(k); } int ask(int k,int l,int r) { if(tree[k].l>r||tree[k].r<l)return 0; if(l<=tree[k].l&&r>=tree[k].r)return tree[k].maxx; int mid=(tree[k].l+tree[k].r)>>1; return max(ask(k<<1,l,r),ask(k<<1|1,l,r)); }//线段树单修区查模版 int main() { scanf("%d %d %d",&n,&m,&k); for(int i=1;i<=k;i++) { scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].num); bj1[i]=a[i].x; bj2[i]=a[i].y; } sort(bj1+1,bj1+k+1); sort(bj2+1,bj2+k+1); int m1=unique(bj1+1,bj1+k+1)-(bj1+1),m2=unique(bj2+1,bj2+k+1)-(bj2+1); n=bj2[m2]; Build(1,1,n); for(int i=1;i<=k;i++) { a[i].x=lower_bound(bj1+1,bj1+m1+1,a[i].x)-bj1; a[i].y=lower_bound(bj2+1,bj2+m2+1,a[i].y)-bj2; }//离散化 sort(a+1,a+k+1,cmp);//按y坐标排序 for(int i=1;i<=k;i++) { int x=ask(1,1,a[i].y)+a[i].num; add(1,a[i].y,x);//将前面的最大值转移到这个点(线段树维护) } printf("%d",ask(1,1,n)); return 0; }