hdu 2089(數位DP)

不要62

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 32234    Accepted Submission(s): 11447

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>
using namespace std;
typedef long long LL;

int dp[10][10];
///預處理dp數組 ,dp[i][j]代表起始位為 j 的 i 位數有多少個.
void init(){
    memset(dp,0,sizeof(dp));
    dp[0][0] = 1;
    for(int i=1;i<=7;i++){ ///最多七位
        for(int j=0;j<=9;j++){ ///第 i 位出現的數字
            for(int k=0;k<=9;k++){ ///第 i - 1的數字
                if(j!=4&&!(j==6&&k==2)){
                    dp[i][j] += dp[i-1][k];
                }
            }
        }
    }
}
int solve(int n){ ///在[0,n)内有多少吉利數
    int dig[10];
    int ans=0;
    int len=1;
    while(n){
        dig[len++] = n%10;
        n/=10;
    }
    dig[len] = 0; ///這個一定要指派，不然WA
    for(int i=len;i>0;i--){ ///枚舉位
        for(int j=0;j<dig[i];j++){ ///枚舉第i位的數字,第i位的數字小于dig[i]
            if(j!=4&&!(dig[i+1]==6&&j==2)){
                ans+=dp[i][j];
            }
        }
        if(dig[i]==4||(dig[i+1]==6&&dig[i]==2)) break;
    }
    return ans;
}
int main(){
    init();
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF,n+m){
        printf("%d\n",solve(m+1)-solve(n));
    }
}