hdu2089 不要62 数位dp

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

题目给出一个区间，询问这个区间中符合要求的数的数量，一般数位dp的文法都是这样，数据量大的情况下可能会有le18，所以一定需要数位dp这样的复杂度在O(logn)量级的算法才能够胜任。

本题给出的要求是数中不含4和62.定义状态dp[i][j]:位数为i的数开头数字为jde符合要求的数的数量，转移方程式：dp[i][j]=sigma（k=0->k=9）(dp[i-1][k]) ,其中要求!(j==6&&k==2)&&j!=4。根据转移方程，我们很容易就能求出[0,n]范围内的符合要求的数的数量。

代码如下：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef unsigned int ui;
 4 typedef long long ll;
 5 typedef unsigned long long ull;
 6 #define pf printf
 7 #define mem(a,b) memset(a,b,sizeof(a))
 8 #define prime1 1e9+7
 9 #define prime2 1e9+9
10 #define pi 3.14159265
11 #define lson l,mid,rt<<1
12 #define rson mid+1,r,rt<<1|1
13 #define scand(x) scanf("%llf",&x) 
14 #define f(i,a,b) for(int i=a;i<=b;i++)
15 #define scan(a) scanf("%d",&a)
16 #define mp(a,b) make_pair((a),(b))
17 #define P pair<int,int>
18 #define dbg(args) cout<<#args<<":"<<args<<endl;
19 #define inf 0x7ffffff
20 inline int read(){
21     int ans=0,w=1;
22     char ch=getchar();
23     while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
24     while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar();
25     return ans*w;
26 }
27 int n,m,t;
28 const int maxn=1e4+10;
29 int digit[20];
30 int len=12;
31 int dp[13][12]; 
32 void init()//预处理dp数组 
33 {
34     dp[0][0]=1;
35     f(i,1,len)
36     {
37         f(j,0,9)
38         {
39             f(k,0,9)
40             {
41                 if(j==4)continue;
42                 if(j==6&&k==2)continue;
43                 dp[i][j]+=dp[i-1][k]; 
44             }
45         }
46     }
47 }
48 int solve(int l)
49 {
50     int ans=0;
51     for(int i=l;i>=1;i--)
52     {
53         f(j,0,digit[i]-1)
54             if(!(digit[i+1]==6&&j==2)&&j!=4)ans+=dp[i][j];
55         
56         if(digit[i]==4||(digit[i]==2&&digit[i+1]==6))break;//当遇到前面固定的数字是4或者62时就不用继续进行枚举了 
57     }
58     return ans;    
59 }
60 int main()
61 {
62     //freopen("input.txt","r",stdin);
63     //freopen("output.txt","w",stdout);
64     std::ios::sync_with_stdio(false);
65     init();
66     while(~scanf("%d%d",&m,&n))
67     {
68         if(n==0&&m==0)return 0;
69         int l=0;
70         n++;//因为上面求得是[0,n)区间的符合要求的数的数量 
71         while(n)
72         {
73             digit[++l]=n%10;
74             n/=10;
75         }
76         digit[l+1]=0;//注意设置l+1的数值，否则上一个样例的数值会影响到这个样例的计算 
77         int ans=solve(l);
78         l=0;
79         while(m)
80         {
81             digit[++l]=m%10;
82             m/=10;
83         }
84         digit[l+1]=0;
85         ans-=solve(l);//实际上求的是[0,m-1]之间的符合条件的数的数量
86         pf("%d
",ans); 
87     } 
88 }