不降数

定义一种不降数，这种数字必须满足从左到右各位数字成小于等于的关系，如123，446。
现在大家决定玩一个游戏，指定一个整数闭区间[a,b] ，问这个区间内有多少个不降数。

输入描述:

有多组测试数据。每组只含两个数字 a，b意义如题目描述,1<=a,b<=2^31

输出描述:

每行给出一个测试数据的答案，即 [a,b] 之间有多少不降数。

示例1
输入

1 9
1 19

输出

9
18

bujiangshu.cppview raw

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
const int N=25;
int digit[N];
LL dp[N][N];
LL dfs(int pos,int statu,int limit)
{
     int i,end,s;
     LL res=0;
     if(pos==-1)
        return 1;
     if(!limit&&dp[pos][statu]!=-1)
        return dp[pos][statu];
     end=limit?digit[pos]:9;
     for(i=statu;i<=end;i++)
         res+=dfs(pos-1,i,limit&&i==end);
     if(!limit)
         dp[pos][statu]=res;
    return res;
}
LL calc(LL n)
{
     int len=0;
     memset(dp,-1,sizeof(dp));
     while(n)
     {
         digit[len++]=n%10;
         n/=10;
     }
     return dfs(len-1,0,1);
}
int main()
{    freopen("data1.in","r",stdin);
     freopen("data1.out","w",stdout);
     LL a,b;
     while(scanf("%lld %lld",&a,&b)!=EOF)
         printf("%lld\n",calc(b)-calc(a-1));
    return 0;
}