Codeforces 960F Pathwalks

题目链接http://codeforces.com/contest/960/problem/F

题意:给定一张有向图,每条边有边权,求一条最长的路径,使得路径上边权严格递增,且路径编号也是递增的(不要求连续),路径的编号就是输入的顺序。

思路:有一个很显然的DP就是dp[i][w]为以节点i为末尾权值不超过w的最长的合法路径,对于每一条指向i的节点u,我们要做的就是找合法的指向u的边,且这条边以u结尾的时候DP值最大,所以我们对每个节点开一个树状数组,下标代表权重,前缀最大和,每次查询的时候就查询u[0,w-1]的前缀最大值然后去更新答案,再拿这个答案去更新v的树状数组的信息即可,然后直接开会炸,所以用map动态开点(新技能get),我们按读入顺序边读入边更新操作就可以去掉路径编号递增这个限制条件了。BTW,看到也有用对每个节点开可持久化线段树的...但好像跟我印象中的不太一样啊..果然是自己理解还不够透彻..

树状数组

const int N=100000+10;
int n,m,i,j,u,v,w,ans;
map<int,int>dp[N];
inline int lowbit(int x){return x&(-x);}
void modify(int id,int x,int v){
    for (;x<=100001;x+=lowbit(x)) dp[id][x]=max(dp[id][x],v); 
}
int query(int id,int x){
    int res=0;
    for (;x;x-=lowbit(x)){
        auto it=dp[id].find(x);
        if (it!=dp[id].end()) res=max(res,dp[id][x]);
    }
    return res;
}
int main(){
    read(n),read(m);
    for (i=1;i<=m;i++){
        read(u),read(v),read(w);
        w++;
        int tmp=query(u,w-1)+1;
        modify(v,w,query(u,w-1)+1);
        ans=max(ans,tmp);
    }
    printf("%d\n",ans);
    return 0;
}

可持久化线段树

const int N=100000+10;
int n,m,i,u,v,w,cnt,ans,root[N],ls[N*20],rs[N*20],mx[N*20];
void ins(int&y,int l,int r,int pos,int val){
    if (!y) y=++cnt;
    mx[y]=max(mx[y],val);
    if (l==r) return;
    int mid=l+((r-l)>>1);
    if (pos<=mid) ins(ls[y],l,mid,pos,val);
    else ins(rs[y],mid+1,r,pos,val);
}
int query(int k,int l,int r,int L,int R){
    if (k==0) return 0;
    if (L<=l&&r<=R) return mx[k];
    int mid=l+((r-l)>>1);
    int ret=0;
    if (L<=mid) ret=max(ret,query(ls[k],l,mid,L,R));
    if (mid<R) ret=max(ret,query(rs[k],mid+1,r,L,R));
    return ret; 
}
int main(){
    read(n),read(m);
    for (i=1;i<=m;i++){
        read(u),read(v),read(w);
        int res=query(root[u],0,100000,0,w-1)+1;
        ins(root[v],0,100000,w,res);
        ans=max(ans,res);
    }
    printf("%d\n",ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注