fzu 2113 Jason的特殊爱好 && hdu 2089 不要62 ( 数位dp )

fzu 2113

#include<cstdio>
#include<iostream>
#include<cstring>

using namespace std;

__int64 dp[20][20],num[20];

__int64 dfs(int pos,int n,bool flag)
{
    if(pos<0) return n;
    if(!flag && dp[pos][n]!=-1) return dp[pos][n];

    int p=flag?num[pos]:9;
    __int64 ans=0;
    for(int i=0;i<=p;i++)
    {
        if(i==1) ans+=dfs(pos-1,n+1,flag && i==p);
        else ans+=dfs(pos-1,n,flag && i==p);
    }
    if(!flag) dp[pos][n]=ans;//n表示pos位前面有多少个1
    return ans;
}

__int64 cal(__int64 x)
{
    int c=0;
    while(x)
    {
        num[c++]=x%10;
        x/=10;
    }
    return dfs(c-1,0,1);
}

int main()
{
    memset(dp,-1,sizeof(dp));
    __int64 l,r;
    while(scanf("%I64d%I64d",&l,&r)!=EOF)
    {
        printf("%I64d\n",cal(r)-cal(l-1));
    }
    return 0;
}

#include<cstdio>
#include<iostream>
#include<cstring>

using namespace std;

int dp[8][2];
int num[8];

int dfs(int pos,bool six,bool flag)  //six 表示上一位是不是6
{
    if(pos<0) return 1;
    if(!flag && dp[pos][six]!=-1) return dp[pos][six];

    int u=flag?num[pos]:9;
    int ans=0;
    for(int i=0;i<=u;i++)
    {
        if(i==4 || (i==2 && six))
            continue;
        ans+=dfs(pos-1,i==6,flag && i==u);
    }
    if(!flag) dp[pos][six]=ans;
    return ans;
}

int cal(int x)
{
    int cnt=0;
    while(x)
    {
        num[cnt++]=x%10;
        x/=10;
    }
    return dfs(cnt-1,0,1);
}

int main()
{
    int l,r;
    memset(dp,-1,sizeof(dp));
    while(scanf("%d%d",&l,&r)!=EOF)
    {
        if(l==0 && r==0) break;
        printf("%d\n",cal(r)-cal(l-1));
    }
    return 0;
}

fzu 2113 Jason的特殊爱好 && hdu 2089 不要62 ( 数位dp )

原文：http://blog.csdn.net/u012841845/article/details/19037909