不要62

1 100
0 0

80

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

int dp[10][15];

void init(){
    int i,j,k;
    memset(dp,0,sizeof dp);
    dp[0][0]=1;
    for(i=1;i<=7;i++)
        for(j=0;j<=9;j++)
            for(k=0;k<=9;k++)
    if(j!=4 && (j!=6 || k!=2))
        dp[i][j]+=dp[i-1][k];
}

int han(int n){
    int digit[10]={0};
    int r=1;
    while(n){
        digit[r++]=n%10;
        n/=10;
    }

    int i,j,k,ans=0;
    for(i=r-1;i>=1;i--){
        for(j=0;j<=digit[i]-1;j++)
            if(j!=4 && (j!=2 || digit[i+1]!=6))
                ans+=dp[i][j];
        if(digit[i]==4 || (digit[i]==2 && digit[i+1]==6))
            break;
    }
    return ans;
}

int main(){
    init();
    int n,m;
    while(cin>>n>>m){
        if(n==0 && m==0)   break;//cout<<han(4)<<endl;
        cout<<han(m+1)-han(n)<<endl;
    }
    return 0;
}

hdu 2089 不要62 DP

原文：http://blog.csdn.net/hyccfy/article/details/43191859