离散化+DP+树状数组P3431【The Bus】

· · 题解

很容易想到O（nm）的DP但是一看m和n的范围10^9，GG

再一看k的范围10^5，便想到离散化一下

//本蒟蒻是用map来离散化的，但是推荐dalao们还是用lower_bound比较好
map<int,int>mpx,mpy;
for(int i=1;i<=k;i++){
    scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].s);
    x[i]=a[i].x;
    y[i]=a[i].y;
    }   
x[0]=y[0]=1;
sort(x,x+k+1);
sort(y,y+k+1);
mpx[x[0]]=++nx;
mpy[y[0]]=++ny; 
for(int i=1;i<=k;i++){
    if(x[i]!=x[i-1])mpx[x[i]]=++nx;
    if(y[i]!=y[i-1])mpy[y[i]]=++ny;
}
for(int i=1;i<=k;i++)a[i].x=mpx[a[i].x],a[i].y=mpy[a[i].y];

此时的复杂度瞬间降到了O（k^2）但是只有40分，怎么办？

不要慌，先将动态转移方程写出来看看^_^

设f[i]表示走到点i的最大值

将数组a以横坐标作为第一关键字，纵坐标作为第二关键字排序后

f[i]=max(f[j])+a[i].s(其间a[j].y<=a[i].y)

亲爱的童鞋们，看到这里是不是想到了什么优化？

树状数组

sort(a+1,a+k+1,cmp);
for(int i=1;i<=k;i++){      
    f[i]=ask(a[i].y)+a[i].s;    
    modify(a[i].y,f[i]);    
}

下面是本蒟蒻的丑代码：

#include<bits/stdc++.h>
using namespace std;
const int A=500005;
map<int,int>mpx,mpy;
struct note{
    int x,y,s;
}a[A];
int n,m,k,ans,x[A],y[A],c[A*4],f[A],nx,ny;
bool cmp(const note&aa,const note&bb){//以横坐标作为第一关键字，纵坐标作为第二关键字排序
    return (aa.x==bb.x?aa.y<bb.y:aa.x<bb.x);
}
///////////////////////////////树状数组 
int lowbit(int x){return x&(-x);}//lowbit操作 
void modify(int x,int k){//单点修改 
    for(int i=x;i<=ny;i+=lowbit(i))c[i]=max(c[i],k);
}
int ask(int x){//区间查询 
    int maxx=0;
    for(int i=x;i;i-=lowbit(i))maxx=max(maxx,c[i]);
    return maxx;
}
///////////////////////////////
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].s);
        x[i]=a[i].x;
        y[i]=a[i].y;
    }
    ///////////////////////////////离散化 
    x[0]=y[0]=1;
    sort(x,x+k+1);
    sort(y,y+k+1);
    mpx[x[0]]=++nx;
    mpy[y[0]]=++ny;
    for(int i=1;i<=k;i++){
        if(x[i]!=x[i-1])mpx[x[i]]=++nx;
        if(y[i]!=y[i-1])mpy[y[i]]=++ny;
    }
    for(int i=1;i<=k;i++)a[i].x=mpx[a[i].x],a[i].y=mpy[a[i].y];
    ///////////////////////////////

    ///////////////////////////////DP 
    sort(a+1,a+k+1,cmp);
    for(int i=1;i<=k;i++){      
        f[i]=ask(a[i].y)+a[i].s;    
        modify(a[i].y,f[i]);    
    }   
    for(int i=1;i<=k;i++)ans=max(ans,f[i]);
    ///////////////////////////////
    printf("%d",ans);
    return 0;
}

结束语：这道题并不难DP+树状数组，但是本蒟蒻却毒瘤了一个小时，结果是粗心将k与n混用了，在此，本蒟蒻提醒您：

代码千万条，细心第一条。

代码不规范，毒瘤两行泪。