不要62
Time Limit : 1000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 1 Accepted Submission(s) : 1
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
杭州人稱那些傻乎乎粘嗒嗒的人為62（音：laoer）。
杭州交通管理局經常會擴充一些的士車牌照，新近出來一個好消息，以後上牌照，不再含有不吉利的數字了，這樣一來，就可以消除個别的士司機和乘客的心理障礙，更安全地服務大衆。
不吉利的數字為所有含有4或62的号碼。例如：
62315 73418 88914
都屬于不吉利号碼。但是，61152雖然含有6和2，但不是62連号，是以不屬于不吉利數字之列。
你的任務是，對于每次給出的一個牌照區間号，推斷出交管局今次又要實際上給多少輛新的士車上牌照了。
Input
輸入的都是整數對n、m（0<n≤m<1000000），如果遇到都是0的整數對，則輸入結束。
Output
對于每個整數對，輸出一個不含有不吉利數字的統計個數，該數值占一行位置。
Sample Input
1 100
0 0
Sample Output
80
Author
qianneng
Source
迎接新學期——超級Easy版熱身賽 想法：數位dp入門題 代碼： #include<stdio.h>
#include<string.h>
int a[20];
int dp[20][2];
int dfs(int pos,int pre,int sum,int limit)
{
if(pos <0)
return 1;
if(!limit && dp[pos][sum] != -1)
return dp[pos][sum];
int up = limit ? a[pos] : 9;
int tmp = 0;
for(int i = 0; i <= up; i++)
{
if(i==2&&pre==6)continue;
if(i==4) continue;
tmp += dfs(pos-1, i,i==6, limit&&(i==a[pos]));
}
if(!limit)
dp[pos][sum] = tmp;
return tmp;
}
int solver(int n)
{
int pos=0;
while(n>0)
{
a[pos++]=n%10;
n/=10;
}
return dfs(pos-1,-1,0,1);
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)&&n+m!=0)
{
memset(dp,-1,sizeof(dp));
printf("%d\n",solver(m)-solver(n-1));
}
return 0;
}