入門(mén)題，見(jiàn)數(shù)位dp入門(mén)

代碼：

#include<iostream>#include<cstdio>#include<cstring>using namespace std;const int maxn = 10;int a[maxn], dp[maxn][3];int dfs(int pos, int PRe, int limit){    if(pos == -1) return 1;    if(!limit && dp[pos][pre] != -1) return dp[pos][pre];    int up = limit ? a[pos] : 9;    int ans = 0;    for(int i = 0; i <= up; i++)    {        if(i == 4) continue;        if(pre == 1 && i == 2) continue;        ans += dfs(pos-1, i == 6, limit && i == a[pos]);    }    if(!limit) dp[pos][pre] = ans;    return ans;}int solve(int x){    int pos = 0;    while(x)    {        a[pos++] = x%10;        x /= 10;    }    return dfs(pos-1, 0, 1);}int main(void){    int n, m;    memset(dp, -1, sizeof(dp));    while(cin >> n >> m, n+m)        printf("%d/n", solve(m)-solve(n-1));    return 0;}
不要62
Time Limit: 1000/1000 MS (java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 39264    Accepted Submission(s): 14280Problem Description杭州人稱(chēng)那些傻乎乎粘嗒嗒的人為62（音：laoer）。杭州交通管理局經(jīng)常會(huì)擴(kuò)充一些的士車(chē)牌照，新近出來(lái)一個(gè)好消息，以后上牌照，不再含有不吉利的數(shù)字了，這樣一來(lái)，就可以消除個(gè)別的士司機(jī)和乘客的心理障礙，更安全地服務(wù)大眾。不吉利的數(shù)字為所有含有4或62的號(hào)碼。例如：62315 73418 88914都屬于不吉利號(hào)碼。但是，61152雖然含有6和2，但不是62連號(hào)，所以不屬于不吉利數(shù)字之列。你的任務(wù)是，對(duì)于每次給出的一個(gè)牌照區(qū)間號(hào)，推斷出交管局今次又要實(shí)際上給多少輛新的士車(chē)上牌照了。 Input輸入的都是整數(shù)對(duì)n、m（0<n≤m<1000000），如果遇到都是0的整數(shù)對(duì)，則輸入結(jié)束。 Output對(duì)于每個(gè)整數(shù)對(duì)，輸出一個(gè)不含有不吉利數(shù)字的統(tǒng)計(jì)個(gè)數(shù)，該數(shù)值占一行位置。 Sample Input
1 1000 0 Sample Output
80 Authorqianneng Source迎接新學(xué)期——超級(jí)Easy版熱身賽 Recommendlcy