HDU 2089 简单数位dp

1、HDU 2089  不要62    简单数位dp

2、总结：看了题解才敲出来的，还是好弱。。

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

int dp[10][11]; //dp[i][j]表示以j为首位符合条件的i位数的个数

void init() //预处理
{
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(int i=1;i<8;i++){
        for(int j=0;j<10;j++){  //枚举第i位
            for(int l=0;l<10;l++){  //枚举第i-1位
                if(j!=4&&(!(j==6&&l==2))){
                    dp[i][j]+=dp[i-1][l];
                }
            }
        }
    }
}

int cal(int num)
{
    int a[10],k=0,sum=0;
    while(num){
        a[++k]=num%10;
        num/=10;
    }

    a[k+1]=0;
    for(int i=k;i>0;i--){
        for(int j=0;j<a[i];j++){  
            if(j!=4&&!(a[i+1]==6&&j==2)){
                sum+=dp[i][j];
            }
        }
        if(a[i]==4||(a[i+1]==6&&a[i]==2)){ //因为是从首位开始，如果前面已经不符合，后面就没必要进行了
            break;
        }
    }

    return sum;
}

int main()
{
    init();
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF,n&&m)
    {
        printf("%d
",cal(m+1)-cal(n));  //cal函数没有考虑到num本身
    }

    return 0;
}