数位DP入门讲解 byLuan

· · 个人记录 

int dfs(int pos,bool qian_dao_0,bool limit,int pre_situation){
    if(!pos) return (the situation is ok)?1:0;
    //如果直接搜到了最后，说明已经填进去的数字都是合法的，只需返回是否满足数字的要求就可以了。
    if(!qian_dao_0 && !limit && visit[pos][situation]) return f[pos][situation];
    //如果这一位的状态已经搜过并且没有前导0，没有填数字的限制，那么就可以直接返回记忆化的值了。
    int lim=limit?numbre[pos]:9,val=0;
    //若这一位有限制，那么只可以填到当前位数字，否则就可以随便填。
    for(int i=0;i<=lim;i++){
        if(situation is not ok) continue;
        //检查当前位填进去的数字是否合法。
        ret+=dfs(pos-1,qian_dao_0&(i==0),limit&(i==lim),situation);
        /*
        前面有提到过，数位DP的记忆化搜索都是从高位向低位确定，这样可以很方便的维护数字大小的上界问题。
        判断有前导0的条件有两个，一个是当前位填0，一个是当前位有前导0。
        判断前面填的数字是否已经到达上界的条件同理，前面和当前位都要达到上界。
        */
    }
    if(!limit && !qian_dao_0){
        visit[pos][situation]=1,f[pos][situation]=val;
    }
    //若没有限制就可以把结果记忆化下来，便于以后调用。
    return val;
}

我们看几道例题了解一下。

Code

inline LL dfs(int pos,bool limit,LL val,bool qd){
    if(pos==0) return 1;
    if((!limit)&&(!qd)&&(f[pos][val])) return f[p][val];
    LL lim=limit?num[p]:9,ans=0;
    for(LL i=0;i<=lim;i++){
        if(abs(val-i)<2) continue;
        ans+=dfs(pos-1,limit&&(i==lim),qd&&(i==0)?-233:i,qd&&(i==0));
    }
    if((!limit)&&(!qd)) f[pos][val]=ans;
    return ans;
}

Code

inline int dfs(int p,int pre,int ppre,bool qd,bool lim,bool hui){
    if(!p) return hui;
    if((!lim)&&(!qd)&&(ppre!=-1)&&(visit[p][pre][ppre][hui])){
        return f[p][pre][ppre][hui];
    }
    int limit=lim?num[p]:9,ret=0;
    for(int i=0;i<=limit;i++){
        bool _hui,_qd;
        _hui=qd?0:hui|(i==pre||i==ppre);
        _qd=qd&(i==0);
        (ret+=dfs(p-1,_qd?-1:i,pre,_qd,lim&(i==limit),_hui))%=mod;
    }
    if((!lim)&&(!qd)&&(ppre!=-1)){
        visit[p][pre][ppre][hui]=true;
        f[p][pre][ppre][hui]=ret;
    }
    return ret;
}

Code

inline LL dfs(LL pos,bool qd,bool lim,LL pre,LL ppre,bool fl,bool ei,bool th){
    if(pos<=0) return ((fl==0||ei==0)&th);
    if((!lim)&&(!qd)&&visit[pos][pre][ppre][fl][ei][th]){
        return f[pos][pre][ppre][fl][ei][th];
    }
    LL limit=lim?num[pos]:9,ret=0;
    for(LL i=0;i<=limit;i++){
        if((i==4&&ei)||(i==8&&fl)) continue;
        bool _qd=qd&(i==0),_lim=lim&(i==limit);
        ret+=dfs(pos-1,_qd,_lim,_qd?-1:i,pre,fl|(i==4),ei|(i==8),th|(i==pre&&i==ppre));
    }
    if((!lim)&&(!qd)){
        visit[pos][pre][ppre][fl][ei][th]=true;
        f[pos][pre][ppre][fl][ei][th]=ret;
    }
    return ret;
}

Code

const int z[10][4]={
    0,0,0,0, 0,0,0,0, 1,0,0,0, 0,1,0,0, 2,0,0,0,
    0,0,1,0, 1,1,0,0, 0,0,0,1, 3,0,0,0, 0,2,0,0
};

inline LL dfs(int pos,int tw,int th,int fi,int se,bool qd,bool lim,LL PI){
    if(pos<=0) return (PI<=r1&&PI>=l1)?1:0;
    if((!lim)&&visit[pos][tw][th][fi][se]){
        return f[pos][tw][th][fi][se];
    }
    LL limit=lim?num[pos]:9,ret=0;
    for(LL i=0;i<=limit;i++){
        bool _qd=qd&(i==0),_lim=lim&(i==limit);
        if((!qd)&&(PI==0||i==0)&&(l1>0)) continue;
        ret+=dfs(pos-1,tw+z[i][0],th+z[i][1],fi+z[i][2],se+z[i][3],_qd,_lim,_qd?1:PI*i);
    }
    if(!lim){
        visit[pos][tw][th][fi][se]=true;
        f[pos][tw][th][fi][se]=ret;
    }
    return ret;
}

Code

inline LL dfs(LL pos,LL v,LL sum,bool lim,LL left,LL mod){
    if(left>pos*9) return 0;
    if(!pos) return (!v);
    if((!lim)&&(~f[pos][sum][v])) return f[pos][sum][v];
    LL limit=lim?num[pos]:9,ret=0;
    for(int i=0;i<=limit;++i){
        if(left<i) break;
        ret+=dfs(pos-1,(v*10+i)%mod,sum+i,lim&(i==limit),left-i,mod);
    }
    if(!lim) f[pos][sum][v]=ret;
    return ret;
}

持更中。