1042 数字0-9的数量(数位DP)

 1042 数字0-9的数量基准时间限制：1 秒 空间限制：131072 KB 分值: 10 难度：2级算法题 收藏 关注 给出一段区间a-b，统计这个区间内0-9出现的次数。比如 10-19，1出现11次（10,11,12,13,14,15,16,17,18,19,其中11包括2个1)，其余数字各出现1次。 Input

两个数a,b（1 <= a <= b <= 10^18)

Output

输出共10行，分别是0-9出现的次数

Input示例

10 19

Output示例

1
11
1
1
1
1
1
1
1
1

并不是完全理解。。。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<limits.h>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<math.h>
#include<map>
using namespace std;
typedef long long ll;
#define maxn 1000005
ll a[15],b[15];
void dfs_dp(ll id,ll num,ll ans[])
{
ll i,j,x,y;
x=id%10;
id/=10;
for(i=0;i<=x;i++)
 ans[i]+=num;
for(i=0;i<=9;i++)
 ans[i]+=num*id;
 ans[0]-=num;//到现在还不是完全明白为啥 
ll t=id;
while(t)
{
ans[t%10]+=(x+1)*num;
t/=10;
}
if(id)
dfs_dp(id-1,num*10,ans);
}
int  main()
{
ll m,n,i,j;
scanf("%lld%lld",&m,&n);
dfs_dp(n,1,a);
dfs_dp(m-1,1,b);
for(i=0;i<=9;i++)
 printf("%lld\n",a[i]-b[i]);
}