hdu2089 하지 마 62 (디지털 dp)

 1 #include <stdio.h>

 2 #include <string.h>

 3 int dp[10][3];

 4 int num[10];

 5 /*

 6 dp[i][0]   62,4

 7 dp[i][1]  2  

 8 dp[i][2]  62 4

 9 */

10 void init()

11 {

12     int i;

13     dp[0][0] = 1;

14     for(i=1; i<10; ++i)

15     {

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

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

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

19     }

20 }

21 int getAns(int n)

22 {

23     int i,len=0,ans=0;

24     int t = n;

25     while(n)

26     {

27         num[++len] = n % 10;

28         n /= 10;

29     }

30     num[len+1] = 0;

31     bool flag = false;

32     

33     for(i=len; i>=1; --i)

34     {

35         ans += num[i] * dp[i-1][2];

36         if(flag)

37         {

38             ans += num[i] * dp[i-1][0];

39         }

40         else if(num[i]>4)//    4

41             ans += dp[i-1][0];

42         if(!flag && num[i]>6)//    6

43             ans += dp[i-1][1];

44         if(!flag && num[i+1]==6&&num[i]>2)

45             ans += dp[i][1];

46         if(num[i+1]==6 && num[i]==2)

47             flag = true;

48         if(num[i]==4)

49             flag = true;

50     }

51     

52     return ans;

53 }

54 int main()

55 {

56     int n,m;

57     init();

58     while(scanf("%d%d",&n,&m))

59     {

60         if(n==0 && m==0)

61             break;

62         

63         int t = getAns(m+1) - getAns(n);

64         printf("%d
",m-n+1-t);

65     }

66     return 0;

67 }