首页 > 代码库 > 数位DP入门：bzoj1833: [ZJOI2010]count 数字计数
数位DP入门：bzoj1833: [ZJOI2010]count 数字计数
膜拜了一下蔡大神。。。。然后突然想起来一些东西然后就填了一个半年多前的坑= =
人生第一道自己写的数位DP。。。好吧以前是看题解然后也不知道为什么就过了的>_<
数位DP介绍：
http://wenku.baidu.com/link?url=9OS5Ybpw5wx00ahrH8ED2oyIlR1uWwrxT8N4pEg27GgBt2T2hLe4sd_h1rmpY7P0HmeHIEDw9h6_K98dPhhjoMhD2TpKcS8w1X8cC_dkPp_
接下来是题目地址：
http://www.lydsy.com:808/JudgeOnline/problem.php?id=1833
题意挺明显。。
首先我萌可以用F[i,j,k]表示有i位数字且前导为k的数中总共含有多少个数字j（0<=j<=9）。。。
然后蒟蒻不想太麻烦（太弱）。。。干脆把1～9拆成9次一次一次来。。。。
因为题目要求的是[l,r],所以答案就是[0,r]-[0,l-1]......
假设当前求的是0～x的数中含有多少个数字num。。。
首先设x有w位数字，把x拆成w位(第一位为最低位)存在数组h里面，然后在处理出x的后i位组合起来是什么数（也就是x的w个后缀）
用pre[i]表示i位数中含有数字i的个数
那么假设处理到第i（i从最高位（w）开始枚举）位：
1、先考虑之后位上的情况：
当第i位取的数字小于h[i]的时候，有h[i]种情况（0～h[i]-1)，此时之后的所有数都可以选（之后不管选什么数都不超过x），所以总个数+=h[i]*pre[i-1]（当前位每一种情况都能给总个数贡献之后位中数字个数）
2、考虑当前位的情况：
如果当前位最大能取的数字=num，由于之前位数都最大，之后的数不能超出x的范围（若之前位数有任意一个小于最大值，那么之后的数可以随便选，则已被上面的步骤计算到），所以能贡献出（当前再后一个后缀的值+1（因为还有一种情况是后面的全选0））个答案。。。。
如果当前位最大能取的数字<num，那么不论之后怎么取，当前这一位都不会贡献任何个数。。。
蒟蒻扯半天最终确定自己是语死早了>_<。。。。
下面是更丑的代码TAT
如果当前位最大能取的数字>num，那么当取的数字为num的时候后面的数可以随便取，且每种情况都会额外贡献一个个数（也就是当前位上的这个）,所以总个数+=10^(i-1)
1 var 2 pre,orz,h,sum:array[0..13]of int64; 3 ans,ans1:array[0..9]of int64; 4 i,j,k,n,m,mid:longint; 5 l,r,tot,tot1,l1,r1,x,w1,w2:int64; 6 procedure mahoshojo(x,num,w:int64); 7 var i:longint;anss:int64; 8 begin 9 anss:=0;10 for i:=1 to w do h[i]:=x div orz[i-1] mod 10;11 for i:=1 to w do sum[i]:=x mod orz[i];12 for i:=w downto 1 do13 begin14 inc(anss,pre[i-1]*h[i]);15 if h[i]>num then inc(anss,orz[i-1]);16 if h[i]=num then inc(anss,sum[i-1]+1);17 end;18 ans[num]:=ans[num]+anss;19 tot:=tot-anss;20 end;21 begin22 pre[1]:=1;23 orz[0]:=1;24 for i:=1 to 13 do orz[i]:=orz[i-1]*10;25 for i:=2 to 13 do pre[i]:=pre[i-1]*10+orz[i-1];26 readln(l,r);27 dec(l);28 tot:=1;29 if l>0 then30 begin31 l1:=l;32 while l1>0 do begin inc(w1);l1:=l1 div 10 end;33 for i:=1 to w1-1 do inc(tot,(orz[i]-orz[i-1])*i);34 if w1>1 then inc(tot,w1*(l-orz[w1-1]+1)) else tot:=l+1;35 end36 else37 w1:=1;38 r1:=r;39 while r1>0 do begin inc(w2);r1:=r1 div 10 end;40 tot1:=1;41 for i:=1 to w2-1 do inc(tot1,(orz[i]-orz[i-1])*i);42 if w2>1 then inc(tot1,w2*(r-orz[w2-1]+1)) else tot1:=r+1;43 // writeln(w2,‘:‘,tot1,‘ ‘,w1,‘:‘,tot);44 for i:=1 to 9 do45 mahoshojo(l,i,w1);46 for i:=1 to 9 do ans[i]:=-ans[i];47 ans[0]:=tot;48 // writeln(‘ ‘,tot);49 tot:=tot1;50 // writeln(‘!!!‘,tot1);51 for i:=1 to 9 do52 mahoshojo(r,i,w2);53 ans[0]:=tot-ans[0];54 for i:=0 to 8 do write(ans[i],‘ ‘);55 writeln(ans[9])56 end.
话说记得类似的还有一道GDOI的题。。。。要求完全相反= =。。。给你1～某个数字中出现的各个数码的次数，要求判断是否存在这个数。。。
反正蒟蒻目测只会二分乱搞TAT.。。。。反正怎么玩都不会TLE2333
//四个月没碰键盘TAT。。。脑子还剩一点但是代码能力已经回档到两年前了>_<
//话说考前复习的时候来填坑显然花样作大死。。。YCL:哪有你这样的学生啊！。。。。。。。。
数位DP入门：bzoj1833: [ZJOI2010]count 数字计数