HDU 2089 不要62 （数位DP）

题目大意

人们将含有62和4的数成为不吉利的数字，大家都不喜欢不吉利的数字。 现给出两个整数n和m，求出从n到m的数字中有多少吉利的数字（不含有62或4的数字）。

解题思路

又是一个数位DP的典型题目，与我之前写过的（HDU 3555 Bomb）相比增加了一点点的难度，判断中需要仔细一点，思路还是相同的。

设立一个二维数组dp[i][j]，保存当数字为i位长的时候的情况，j=0表示不含有62且不含有4且不以2开头的数，j=1代表不含有62且不含有4但以2开头的数字的个数，j=2代表含有62或4的数（不吉利的数字）的个数。

转移方程：

dp[i][0]=9*dp[i-1][0]-dp[i-1][1];

//在i-1位数的基础上构造i位数时，首位可以添加处4以外的数字，还要减去添加的数位6且原首位为2的情况。

dp[i][1]=dp[i-1][0];

//在原基础上首位添加数字为2，已经包含了原来首位为2的情况，所以不需要另外考虑。

dp[i][2]=10*dp[i-1][2]+dp[i-1][1]+dp[i-1][0];

//原有的62增加任意首位+原有首位为2添加6构成62+原有任意首位添加4的情况。

附上代码：

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int dp[100][3],n,m,num[20]; void init() { memset(dp,0,sizeof(dp)); dp[0][0]=1; for(int i=1;i<=10;i++){ dp[i][0]=9*dp[i-1][0]-dp[i-1][1]; dp[i][1]=dp[i-1][0]; dp[i][2]=10*dp[i-1][2]+dp[i-1][1]+dp[i-1][0]; } } int solve(int k) { memset(num,0,sizeof(num)); int ans=0,cont=0,temp=k; while(k){ num[++cont]=k%10; k/=10; }//将原来的数字分成不同的位存到数组中 bool flag=false; for(int i=cont;i>=1;i--){ ans+=num[i]*dp[i-1][2];//计算的是比当前位小的数字的情况 if(flag)//如果已经存在62或者4 ans+=dp[i-1][0]*num[i];//当前位后的位可以随意构造 else{ if(num[i]>4) ans+=dp[i-1][0];//只计算当前位为4的全部数字 if(num[i+1]==6&&num[i]>2) ans+=dp[i][1];//只计算当前两位为62的全部数字 if(num[i]>6) ans+=dp[i-1][1];//计算当前位为6的以2开头的数字 } //***以上三种并不相互包含。 if(num[i]==4||(num[i+1]==6&&num[i]==2)) flag=true; } return temp-ans; } int main() { int ans1,ans2,ans; init(); while(~scanf("%d%d",&n,&m),n+m) { ans1=solve(n); ans2=solve(m+1); ans=ans2-ans1; printf("%d\n",ans); } return 0; }