hdu2089 싫어 62 [디지털 dp]

사실은 어제 오후에 썼는데 급하게 갔어요 블로그를 안 썼어요==이전의 디지털 dp는 모두 2진법이에요. 다른 유형으로 바꾸면 클래식이라고 할 수 있죠. 사실 본질은 다 똑같아요.

/*************
hdu2089
2016.2.17
0MS	1568K	1220 B	G++
*************/
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[10][11];
void init()
{
    f[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))
                    f[i][j]=f[i-1][k]+f[i][j];
        }
    }
}
void print()
{
    for(int i=0;i<=7;i++)
    {
        for(int j=0;j<=9;j++)
        printf("i=%d j=%d f=%d
",i,j,f[i][j]);
    }
}
int cal(int x)
{
    int digit[10],num=0,sum=0;
    memset(digit,0,sizeof(digit));
    while(x)
    {
        digit[num++]=x%10;
        x/=10;
    }
    digit[num]=0;
    for(int i=num-1;i>=0;i--)
    {
        for(int j=0;j<digit[i];j++)
        {
            if(j!=4&&!(j==2&&digit[i+1]==6)) sum+=f[i+1][j];
        }
        if(digit[i]==4||(digit[i]==2&&digit[i+1]==6)) break;
    }
    return sum;
}
int main()
{
    freopen("cin.txt","r",stdin);
    int n,m;
    init();
    //print();
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0&&m==0) break;
        printf("%d
",cal(m+1)-cal(n));
    }
    return 0;
}