ACdream 1083 完美树

http://acdreamoj.sinaapp.com/problem.php?id=1083
第一道数位dp 感触很深；
 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int  arr[11],num[11][4];
 8 bool vis[11][4];
 9 
10 
11 int judge( int stu,int i)
12 {
13     if( i == 3 ) return (stu|1);
14     if( i == 8 ) return (stu|2);
15     return stu;
16 }
17 
18 int DFS( int pos,int stu ,bool full )
19 {
20     int res = 0,i;
21     if( pos == -1 )
22     {
23         if(stu == 1 || stu == 2) return 1;
24         return 0;
25     }
26     if( !full && vis[pos][stu] ) return  num[pos][stu];
27     int Max = full?arr[pos]:9;
28     for( i = 0; i <= Max; i++ )
29       res += DFS( pos-1,judge( stu,i ),full && ( i == arr[pos] ) );
30     num[pos][stu] = res;
31     vis[pos][stu] = true;
32     return res;
33 }
34 
35 int solve( int X )
36 {
37     int k = 0;
38     memset( vis,false,sizeof(vis) );
39     memset( num,0,sizeof(num) );
40     while( X )
41     {
42         arr[k++] = X%10;
43         X /=10;
44     }
45     return DFS( k-1,0,true );
46 }
47 int main( )
48 {
49     int T,L,R;
50     scanf("%d",&T);
51     while( T-- )
52     {
53         scanf("%d%d",&L,&R);
54         printf("%d\n",solve(R) - solve(L-1) );
55     }
56     return 0;
57 }