Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5969    Accepted Submission(s): 1886

题目链接：

HDU - 4722 

题目描述：

输入两个数A,B，判断从A到B之间有多少个数的各个位数上数字的和能够整除10

题解：

for(int i=le;i<=ri;i++)
        if(right(i)) ans++;

上面的方法是直接枚举，那这种方法可行不可行？

A，B的范围是1e18，那么这道题趋于时间的限制不能使用枚举法！

不过可以采用数位DP的方法去做这道题。

如果你对数位DP比较陌生的话，可以参考一下这篇博客

现在想要计算A到B中有多少个符合要求的数字，只需

solve(ri)-solve(le-1)

就行了！

很神奇吧，哈哈。

ll solve(ll x)
{
   int pos=0;//代表位数
   while(x)
   {
       a[pos++]=x%10;
       x/=10;
   }
   return dfs(pos-1,0,1);//因为是pos++,所以这里pos-1，这里已经是最高位了，这位的前面应该是0。
}

这里是solve（）函数，这个函数的目的就是计算当前数之前有多少个数符合要求！

既然是数位DP，那就要说说什么是数位，就像123,1为百位，2位十位，3为个位，对每一位进行操作，然后结合dp进行优化。

那接下来有一个难点就是dfs(pos-1,0,1)了，1代表的是当前是最高位，比如说123，百位可以取0和1，如果说我现在取了1的话，这个时候dfs传入的就是1了，为什么呢？

举个例子：如果现在百位取1，那么我们的十位就只能取0/1/2，如果说现在百位取0，那么我们的十位就能取0-9里面的任意一个数，那么现在传入的1就代表我们后面要对前面位数上是不是最大数进行特判。

搜索函数如下：

#include<algorithm>
#include<cstdio>
#include<string.h>
#include<string>
#include<iostream>
using namespace std;
typedef long long ll;
int a[25];
ll dp[25][20];

ll dfs(int pos,int state,int limit)//limit判断是否达到上限
{
    if(pos==-1) return state==0;//如果pos==-1的话，就代表结束了,开始回溯
    if(!limit&&dp[pos][state]!=-1)//没有达到上限且存在
        return dp[pos][state];
    int up=limit?a[pos]:9;//计算下一位的位数
    ll ans=0;
    for(int i=0;i<=up;++i)
    {
        /*
        数位DP的模板上面这里有判断的条件，这道题可以直接用state解决。
        前面有一句if(pos==-1) return state==0;
        因为每一步进行的操作是(state+i)%10,所以只需使最后等于0就满足
        题目要求了，这样直接可以让ans++；
        */
        ans+=dfs(pos-1,(state+i)%10,limit&&i==up);
    }
    if(!limit) dp[pos][state]=ans;
    return ans;
}

ll solve(ll x)
{
   int pos=0;//代表位数
   while(x)
   {
       a[pos++]=x%10;
       x/=10;
   }
   return dfs(pos-1,0,1);//因为是pos++,所以这里pos-1，这里已经是最高位了，这位的前面应该是0。
}

int main()
{
    ll le,ri;
    int n;
    cin>>n;
    int number=0;
    memset(dp,-1,sizeof(dp));
    while(n--)
    {
        scanf("%I64d%I64d",&le,&ri);
        if(le!=0)
          printf("Case #%d: %I64d\n",++number,solve(ri)-solve(le-1));
        else
          printf("Case #%d: %I64d\n",++number,solve(ri));
    }
    return 0;
}