数位dp入门 HDU 2089 HDU 3555

时间:2024-07-03 00:05:14

  最基本的一类数位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