fzu 2113 Jason的特殊爱好 --- 数位dp

这题目名字起的真龊。。。

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll __int64
using namespace std;

ll dp[30][20],a,b,num[30];

ll dfs(ll n,ll pos,bool flag)
{
    if(pos==-1) return n;
    if(!flag&&dp[pos][n]!=-1) return dp[pos][n];
    ll ans=0,p;
    if(flag) p=num[pos];
    else p=9;
    for(ll i=0;i<=p;i++)
    {
        if(i==1) ans+=dfs(n+1,pos-1,flag&&i==p);//这里写成了num[i] 一直错 终于理解了这个dfs
        else ans+=dfs(n,pos-1,flag&&i==p);
    }
    if(!flag) dp[pos][n]=ans;
    return ans;
}

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


int main()
{
    memset(dp,-1,sizeof dp);
    while(~scanf("%I64d%I64d",&a,&b))
    {
        if(a>b) swap(a,b);
        printf("%I64d\n",cal(b)-cal(a-1));
    }
    return 0;
}

fzu 2113 Jason的特殊爱好 --- 数位dp

原文：http://blog.csdn.net/u011032846/article/details/18798733