hdu 2089 62桁dp不要

8951 ワード

いいえ62
Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 19640    Accepted Submission(s): 6697
Problem Description
杭州人はバカな人を62人と呼んでいる.
杭州交通管理局はよくタクシーのナンバープレートを拡充して、最近良いニュースが出てきて、後でナンバープレートをつけて、もう不吉な数字を含んでいません.そうすれば、個別のタクシーの運転手と乗客の心理的な障害を解消して、もっと安全に大衆にサービスすることができます.
不吉な数字は4または62を含むすべての番号です.例:
62315 73418 88914
いずれも不吉な番号に属している.ただし、61152は6と2を含んでいるが62連番ではないので不吉な数字の列ではない.
あなたの任務は、毎回与えられたナンバープレート区間番号について、交管局が今回また実際に何台の新しいタクシーにナンバープレートを与えたかを推定することです.
 
 
Input
入力はすべて整数対n,m(0 
 
Output
各整数ペアについて、1行の位置を占める不吉な数字を含まない統計個数を出力します.
 
 
Sample Input
1 100 0 0
 
 
Sample Output
80
 
标题:統計区間[L,R]は4または62の個数を含まない.
構想:dp[i][j]は数字長がiの場合、最高位がjの場合の合理的な案数を表す.
 1 #include<iostream>

 2 #include<stdio.h>

 3 #include<cstring>

 4 #include<cstdlib>

 5 using namespace std;

 6 

 7 int dp[7][10];

 8 int hxl[10],hlen;

 9 void init()

10 {

11     dp[0][0]=1;

12     for(int i=1;i<=6;i++)//     

13     {

14         for(int j=0;j<=9;j++)//  i     

15         {

16             for(int s=0;s<=9;s++)/** i -1 **/

17                 if(j!=4 && !(j==6&&s==2))

18                 dp[i][j] = dp[i][j] +dp[i-1][s];

19         }

20     }

21 }

22 int solve(int k)

23 {

24         hlen = 0;

25         while(k)

26         {

27             hxl[++hlen] = k%10;

28             k = k/10;

29         }

30         int sum = 1;

31         for(int i=hlen;i>=1;i--)

32         {

33             for(int j=0;j<hxl[i];j++)

34                 if(j!=4 && !(i+1<=hlen&&j==2&&hxl[i+1]==6))

35                 sum = sum+dp[i][j];

36             if(hxl[i]==4 || (i+1<=hlen&&hxl[i]==2 && hxl[i+1]==6)){

37                     sum --;

38                     break;

39             }

40         }

41         return sum;

42 }

43 int main()

44 {

45     int n,m;

46     init();

47 

48     while(scanf("%d%d",&n,&m)>0)

49     {

50         if(n==0&&m==0)break;

51         printf("%d
",solve(m)-solve(n-1)); 52 } 53 return 0; 54 }