不要62

1 1000 0 Sample Output
80 數位DP能比較好地解決某范圍內滿足要求的數字一個比較普遍的套路dp[i][j]表示以j開頭的i位數中滿足要求的個數一般的轉移表達式為dp[i][j]=∑(k=0-9)dp[i-1][k]此題中任何j=4的情況都是等于0，而后在j=6,k=2的情況下不參與轉移式計算以下為代碼：#include <stdio.h>int dp[10][10]={0},num[10]={0};int main(){    int n[2],ans[2],len,i,j,k;    dp[0][0]=1;    for (int i = 1; i <= 7; ++i)        for (int j = 0; j <= 9; ++j)            for (int k = 0; k <= 9; ++k)                if (j != 4 && !(j == 6 && k == 2))                    dp[i][j] += dp[i - 1][k];    while (scanf("%d%d", &n[0], &n[1]) == 2) {        if(n[0]==0&&n[1]==0)            break;        n[1]++;        for(k=0;k<2;k++){            len=0;            ans[k]=0;            while(n[k]){                num[++len]=n[k]%10;                n[k]/=10;            }            num[len+1]=0;            for(i=len;i>=1;i--){                for(j=0;j<num[i];j++){                    if(num[i+1]!=6||j!=2)                    ans[k]+=dp[i][j];                }                if(num[i]==4||(num[i+1]==6&&num[i]==2))                    break;            }        }        printf("%d/n",ans[1]-ans[0]);    }}