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の場合の合理的な案数を表す.
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 }