数位DP

---

Orz 

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

1 //BZOJ 1833 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #define rep(i,n) for(int i=0;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\n",getans(b,9)-getans(a-1,9));49 return 0;50 }