HDU 2089 不要62：数位dp

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2089

题意：

　　问你在区间[n,m]中，有多少个数字不含"4"且不含"62"。

题解：

　　表示状态：

　　　　dp[i][j] = numbers

　　　　数字有i位，开头为数字j，合法的数字个数。

　　如何转移：

　　　　dp[i][j] = ∑ dp[i-1][k]　　(j!=4,6 && k!=4)

　　　　dp[i][6] = ∑ dp[i-1][k]　　(k!=2,4)

　　　　dp[i][4] = 0

　　边界条件：

　　　　dp[0][0] = 1

　　找出答案：

　　　　题目中询问的是区间，所以答案可以用差分形式表示：

　　　　　　ans = cal_ans(m+1) - cal_ans(n)

　　　　　　cal_ans(i)表示小于i的合法数字个数。

　　　　比如我要求小于32768的合法数字个数：

　　　　　　ans += 0xxxx, 1xxxx, 2xxxx的个数

　　　　　　ans += 30xxx, 31xxx的个数

　　　　　　ans += 320xx, 321xx, 322xx, 323xx, 324xx, 325xx, 326xx的个数

　　　　　　ans += 3270x, 3271x, 3272x, 3273x, 3274x, 3275x的个数

　　　　　　ans += 32760, 32761, 32762, 32763, 32764, 32765, 32766, 32767的个数（均为1）

　　　　所以依次枚举i（从len到1），意思是i+1位之前的数字都已确定，该枚举第i位了。

　　　　枚举第i位的数字为j。ans+=dp[i][j]的条件是前一位和当前位不能构成"62"，即：d[i+1]!=6 || j!=2

　　　　并且，一旦(d[i]==4 || (d[i+1]==6 && d[i]==2))，就应退出循环，因为之后枚举的数字一定都是不合法的。

AC Code:

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #define MAX_L 10
 5 #define MAX_D 15
 6 
 7 using namespace std;
 8 
 9 int n,m;
10 int d[MAX_L];
11 int dp[MAX_L][MAX_D];
12 
13 void cal_dp()
14 {
15     memset(dp,0,sizeof(dp));
16     dp[0][0]=1;
17     for(int i=1;i<=7;i++)
18     {
19         for(int j=0;j<=9;j++)
20         {
21             for(int k=0;k<=9;k++)
22             {
23                 if(j!=4 && (j!=6 || k!=2))
24                 {
25                     dp[i][j]+=dp[i-1][k];
26                 }
27             }
28         }
29     }
30 }
31 
32 int cal_ans(int x)
33 {
34     int len=0;
35     int ans=0;
36     while(x)
37     {
38         d[++len]=x%10;
39         x/=10;
40     }
41     d[len+1]=0;
42     for(int i=len;i>0;i--)
43     {
44         for(int j=0;j<d[i];j++)
45         {
46             if(d[i+1]!=6 || j!=2) ans+=dp[i][j];
47         }
48         if(d[i]==4 || (d[i+1]==6 && d[i]==2)) break;
49     }
50     return ans;
51 }
52 
53 int main()
54 {
55     cal_dp();
56     while(cin>>n>>m)
57     {
58         if(n==0 && m==0) break;
59         cout<<cal_ans(m+1)-cal_ans(n)<<endl;
60     }
61 }