数位DP(学习笔记)

洛咕日报这篇博客写得很好,蒟蒻在这里学会了

摘自上面那篇博客的模板:不过我一般不记录\(st\)这个值,而是在\(pos>len\)时直接返回1,表示找到了一个合法的数.

ll dfs(int pos,int pre,int st,……,int lead,int limit){//记搜
    if(pos>len) return st;//剪枝
    if((dp[pos][pre][st]……[……]!=-1&&(!limit)&&(!lead))) return dp[pos][pre][st]……[……];//记录当前值
    ll ret=0;//暂时记录当前方案数
    int res=limit?a[len-pos+1]:9;//res当前位能取到的最大值
    for(int i=0;i<=res;i++){
        //有前导0并且当前位也是前导0
        if((!i)&&lead) ret+=dfs(……,……,……,i==res&&limit);
        //有前导0但当前位不是前导0，当前位就是最高位
        else if(i&&lead) ret+=dfs(……,……,……,i==res&&limit);
        else if(根据题意而定的判断) ret+=dfs(……,……,……,i==res&&limit);
    }
    if(!limit&&!lead) dp[pos][pre][st]……[……]=ret;//当前状态方案数记录
    return ret;
}
ll part(ll x){//把数按位拆分
    len=0;
    while(x) a[++len]=x%10,x/=10;
    memset(dp,-1,sizeof dp);//初始化-1（因为有可能某些情况下的方案数是0）
    return dfs(……,……,……,……);//进入记搜
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%lld%lld",&l,&r);
        if(l) printf("%lld",part(r)-part(l-1));//[l,r](l!=0)
        else printf("%lld",part(r)-part(l));//从0开始要特判
    }
    return 0;
}

HDU-不要62

题意:每次给定\(n,m\)一对数,求\([n,m]\)内不含4也不含62的数的个数.\(0<=n<=m<=1e7.\)

分析:直接套模板就好了.记得要特判\(n=0\)的情况.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
int n,m,len;
int a[10],dp[10][10];
inline ll dfs(int pos,int pre,int lead,int limit){
    if(pos>len)return 1;//找到了一个合法的数
    if(dp[pos][pre]!=-1&&(!lead)&&(!limit))return dp[pos][pre];//记忆化搜索
    int cnt=0,res=limit?a[len-pos+1]:9;
    for(int i=0;i<=res;++i){//枚举当前pos数位上能填的数
        if(i==4)continue;//数字中不能含4
        if(pre==6&&i==2)continue;//也不能有62
        if((!i)&&lead)cnt+=dfs(pos+1,0,1,limit&&(i==res));
        else if(i&&lead)cnt+=dfs(pos+1,i,0,limit&&(i==res));
        else cnt+=dfs(pos+1,i,0,limit&&(i==res));
    }
    return (!limit&&!lead)?dp[pos][pre]=cnt:cnt;
}
inline int part(int x){
    len=0;while(x)a[++len]=x%10,x/=10;
    memset(dp,-1,sizeof(dp));
    return dfs(1,0,1,1);
}
int main(){
    while(1){
        n=read(),m=read();if(!n&&!m)break;
        if(!n)printf("%d\n",part(m)-part(1)+1);//特判
        else printf("%d\n",part(m)-part(n-1));
    }
    return 0;
}