hdu2089 (디지털 dp)

제목: 구간에 62와 4의 수가 없는 개수를 구한다.
해법: 디지털 dp.
int dfs(int pos,int pre,bool limit,bool have).pos는 dp에서 오는 디지털 위치를 나타내고pre는 앞의 디지털 위치를 나타낸다.limit은 이 시간수가 떨어졌는지(이 위치의 숫자가 제한되었는지의 의미), have는 이전에 62가 있었는지 여부를 나타낸다.4의 배제는 매번 다음 i를 열거할 때마다 4를 얻지 않으면 된다.모든 케이스의 dp값은 같기 때문에 한 번만 계산해야 한다.
코드:

/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <string.h>
//freopen ("in.txt" , "r" , stdin);
using namespace std;

#define eps 1e-8
const double pi=acos(-1.0);
typedef long long LL;
const int Max=10100;
const int INF=1000000007;
int dp[15][12];
int num[20];
int p=0;
int dfs(int pos,int pre,bool limit,bool have)
{
    if(pos==0)
        return !have;
    if(have)
        return 0;
    if(!limit&&dp[pos][pre]!=-1)
        return dp[pos][pre];
    int en=limit?num[pos-1]:9;
    int ans=0;
    for(int i=0; i<=en; i++)
    {
        if(i==4)continue;
        ans+=dfs(pos-1,i,limit&&i==en,(pre==6&&i==2));
    }
    if(!limit)
        return dp[pos][pre]=ans;
    else
        return ans;
}
int getans(int t)
{
    if(t==0)
        return 0;
    p=0;
    while(t)
    {
        num[p++]=t%10;
        t/=10;
    }
    int ans=0;
    for(int i=0; i<=num[p-1]; i++)
    {
        if(i==4)
            continue;
        ans+=dfs(p-1,i,i==num[p-1],0);
    }
    return ans-1;
}

int main()
{
    int l,r;
    memset(dp,-1,sizeof dp);
    while(scanf("%d%d",&l,&r)==2)
    {
        if(r==0&&l==0)
            break;
        cout<<getans(r)-getans(l-1)<<'
';
    }
    return 0;
}