最基本的一类数位dp题，题目大意一般是在a~b的范围，满足某些要求的数字有多少个，而这些要求一般都是要包含或者不包含某些数字，或者一些带着数字性质的要求，一般来说暴力是可以解决这一类问题，可是当范围非常大时，暴力明显会超时，这时便是需要把它转化为一类dp问题，这就是数位dp。像一个数1234567890，直接把它暴力的话，那它就是一个1e9级别的数，可是把它一个数位一个数位的话，那它就是1位是0,2为是9，一直到10位是1，一共才10位的长度，明显就比暴力明朗多了。
由于我也是刚接触不久，还没有什么自己深刻感悟，日后再做总结，现在先具体问题具体分析，来两道入门的数位dp题进行进行理解
不要62和4HDU - 2089
题目大意就是，一个数字它如果含有62或者4它就是不吉利数字，而你要求的就是【n,m】范围内的不含有不吉利数字的个数。
这题的范围只有1e6，所以暴力还是行得通的，不过我们在学数位dp，就用数位dp来解决。那我们想一下，每一个数个位，十位，百位。。。的范围都是从0~9,那么我们把一个数拆成一位位，例如，一个万位的数就可以拆成
万：0 1 2 3 4 5 6 7 8 9
千：0 1 2 3 4 5 6 7 8 9
百：0 1 2 3 4 5 6 7 8 9
十：0 1 2 3 4 5 6 7 8 9
个：0 1 2 3 4 5 6 7 8 9
现在假如一个数的10086，那它的范围内有多少个不含不吉利吉利的数呢，首先我们得把10086分解，得出一个上界，类似这个样子
万：0 1 2 3 4 5 6 7 8 9 上界1
千：0 1 2 3 4 5 6 7 8 9 上界0
百：0 1 2 3 4 5 6 7 8 9 上界0
十：0 1 2 3 4 5 6 7 8 9 上界8
个：0 1 2 3 4 5 6 7 8 9 上界6
这个上界就是在有限制的情况下，当前数位的数字选择只能从[0,上界]中选择，那么这个限制又是什么吗，其实就是范围限制，就像现在我们要求的是10086范围内的，那么如果万位取0，对千位肯定就没有限制可以取[0,9]中任意的数字，但当万位取1，千位就有限制了只能取到0，要是取到1那么就不是求10086范围内的了，而是求11xxx范围内的了，那这个限制怎么传递呢，首先当前数位如果没有限制的话，那么对下面的数位也没有限制，像万位取0,下面的数位都没有限制，而当前数位如果有限制的话，并且取的是上界的话，对下面的数位就有限制，像万位取1，千位有限制，然后千位取0是上界又对下面的又有限制，而像万位取1，千位取0，百位取0，对十位有限制，但十位取小于8的数对个位就没有限制，所以上界的限制传递的条件就是，当前数位有限制并且取的是上界，就会对下面的数位有限制
那现在回到问题，怎么确定不是不吉利的数有几个呢，首先每一位肯定是不能含有4这个数字的，然后就是上一数位是6，当前数位就不能是2，详情见代码
#include<cstdio>
#include<cstring>
int n,m,up[],dp[][];//dp[i][j]数位i的上一数字是不是6时不含不吉利的数字有多少个
int dfs(int p,bool is6,bool isu)//p当前数位，is6上一个数位是不是6,isu当前数位有没有限制
{
if(p==)//边缘值，p为0是个空集，肯定没有62或4，返回1
return ;
if(!isu&&dp[p][is6]!=-)
return dp[p][is6];
int ans=;
for(int i=;i<=(isu ? up[p] : );i++)
{
if((is6&&i==)||i==)//当前数位不能取4，以及如果上一数位取6，当前数位不能取9
continue;
ans+=dfs(p-,i==,isu&&i==up[p]);//继续往下判断下一数位
}
if(!isu)
dp[p][is6]=ans;
return ans;
}
int solve(int x)
{
int num=;
while(x)
{
up[++num]=x%;
x/=;
}
return dfs(num,,);
}
int main()
{
memset(dp,-,sizeof(dp));
while(scanf("%d%d",&n,&m)&&(n||m))
printf("%d\n",solve(m)-solve(n-));
return ;
}
666
关于记忆化，当前数位没有限制时，那么它取任何数相对应的结果是通用的，记忆化搜索就达到了省时的效果
要49HDU - 3555
相比上一题不要62和4，这题就是给出一个n,要求[1,n]范围内含49的数字有多少个，不过我们可以反过来求出不含49的，然后减去即可
#include<cstdio>
#include<cstring>
#define ll long long
ll n,dp[][];
int t,up[];
ll dfs(int p,bool is4,bool isu)
{
if(p==)
return ;
if(!isu&&dp[p][is4]!=-)
return dp[p][is4];
ll ans=;
for(int i=;i<=(isu ? up[p] : );i++)
{
if(is4&&i==)
continue;
ans+=dfs(p-,i==,isu&&i==up[p]);
}
if(!isu)
dp[p][is4]=ans;
return ans;
}
ll solve(ll x)
{
int num=;
while(x)
{
up[++num]=x%;
x/=;
}
return dfs(num,,);
}
int main()
{
scanf("%d",&t);
memset(dp,-,sizeof(dp));
while(t--)
{
scanf("%lld",&n);
printf("%lld\n",n+-solve(n));
}
return ;
}
999
对于答案的+1,因为我们的数位dp求的是[0,n]范围内的不含49的数字的个数，而题目要求的是[1,n]范围内含49的数字的个数，直接用n减去的话，0肯定不含49，会多减去一个0，所以要+1
当然也有直接就是求[1,n]范围内含49的数字个数的，详情见代码
#include<cstdio>
#include<cstring>
#define ll long long
ll n,dp[][],cf[]={};//cf保存10的次方
int t,up[];
ll dfs(int p,bool is4,bool isu)
{
if(p==)//空集不含49，返回0
return ;
if(!isu&&dp[p][is4]!=-)
return dp[p][is4];
ll ans=;
for(int i=;i<=(isu ? up[p] : );i++)
{
if(is4&&i==)//上一数位的4，当前位是9，可以计算答案了
ans+=isu ? n%cf[p-]+ : cf[p-];//有上界的限制，比如n是49870，
//当前位是第4位取9，那么49000~49870都是可以的，也就是n%1000+1
//反之没有限制的话，比如n是50000,当第5位是4，当前位是第4位取9
//那么49000~49999都是可以的，也就是1000
else
ans+=dfs(p-,i==,isu&&i==up[p]);
}
if(!isu)
dp[p][is4]=ans;
return ans;
}
ll solve(ll x)
{
int num=;
while(x)
{
up[++num]=x%;
x/=;
}
return dfs(num,,);
}
int main()
{
for(ll i=;i<=;i++)
cf[i]=cf[i-]*;
scanf("%d",&t);
memset(dp,-,sizeof(dp));
while(t--)
{
scanf("%lld",&n);
printf("%lld\n",solve(n));
}
return ;
}
999