【BZOJ】【1833】【ZJOI2010】count 数字计数

数位DP

学习了一下用记忆化搜索来捉题的新姿势……但没学会TAT，再挖个坑（妈蛋难道对我来说数位DP就是个神坑吗……sigh）

 1 //BZOJ 1833
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<iostream>
 6 #include<algorithm>
 7 #define rep(i,n) for(int i=0;i<n;++i)
 8 #define F(i,j,n) for(int i=j;i<=n;++i)
 9 #define D(i,j,n) for(int i=j;i>=n;--i)
10 using namespace std;
11 typedef long long LL;
12 LL getint(){
13     LL v=0,sign=1; char ch=getchar();
14     while(ch<'0'||ch>'9') {if (ch=='-') sign=-1; ch=getchar();}
15     while(ch>='0'&&ch<='9') {v=v*10+ch-'0'; ch=getchar();}
16     return v*=sign;
17 }
18 /*******************tamplate********************/
19 
20 
21 LL f[100],c[100],a[100],p[100];
22 LL dfs(int x,int dig,int front,int line){
23     if (!x) return 0;
24     if (!front && !line && f[x]!=-1) return f[x];
25     LL last=(line ? a[x] : 9), tot=0;
26     F(i,0,last){
27         if (front && i==0) tot+=dfs(x-1,dig,1,line&&i==last);
28         else if (i==dig){
29             if (i==last && line) tot+=c[x-1]+1+dfs(x-1,dig,0,line && i==last);
30             else tot+=p[x-1]+dfs(x-1,dig,0,line && i==last);
31         }
32         else tot+=dfs(x-1,dig,0,line&& i==last);
33     }
34     if (!front && !line) f[x]=tot;
35     return tot;
36 }
37 LL getans(LL x,LL dig){
38     memset(f,-1,sizeof f);
39     LL t=x; int len=0;
40     while(t) a[++len]=t%10,t/=10,c[len]=c[len-1]+a[len]*p[len-1];
41     return dfs(len,dig,1,1);
42 }
43 int main(){
44 //    freopen("input.txt","r",stdin);
45     LL a=getint(),b=getint();
46     p[0]=1; F(i,1,15) p[i]=p[i-1]*10;
47     rep(i,9) printf("%lld ",getans(b,i)-getans(a-1,i));
48     printf("%lld
",getans(b,9)-getans(a-1,9));
49     return 0;
50 }

View Code