首页 > 代码库 > SCOI2009windy数
SCOI2009windy数
数位DP,还不怎么会……
其中calc函数的计算分为三部分:
第一部分:统计最高位为0的情况,或者说不足最高位位数的数的个数
第二部分:统计最高位为1到a[len]-1的情况,直接调用数组即可
第三部分:统计与x前(len-i)位相同,但剩下的不同的满足条件的数
这里用到了一个技巧,就是虚开实用,就像虚数的起源那样
f[i,0]如果直接看是没有什么意义的,那个数字开头会为0?
可是这样开了的话,f[i,j]:=f[i,j]+f[i-1,k]j就可以很好的利用
或者我们可以把f[i,j]理解为长度为i的字符串,首字符为j的满足条件的字符串的个数
代码:
1 var i,j,k,x,y:longint; 2 f:array[-1..15,-1..15] of longint; 3 function calc(x:longint):longint; 4 var i,j,len:longint; 5 st:string; 6 a:array[0..15] of longint; 7 begin 8 if x=0 then exit(0); 9 str(x,st);10 len:=length(st);11 calc:=0;12 for i:=1 to len do a[i]:=ord(st[len+1-i])-48;13 for i:=1 to len-1 do14 for j:=1 to 9 do15 inc(calc,f[i,j]);16 for i:=1 to a[len]-1 do17 inc(calc,f[len,i]);18 for i:=len-1 downto 1 do19 begin20 for j:=0 to a[i]-1 do21 if abs(a[i+1]-j)>=2 then inc(calc,f[i,j]);22 if abs(a[i+1]-a[i])<2 then break;23 end;24 end;25 procedure main;26 begin27 for i:=0 to 9 do f[1,i]:=1;28 for i:=2 to 10 do29 for j:=0 to 9 do30 for k:=0 to 9 do31 if abs(j-k)>=2 then f[i,j]:=f[i,j]+f[i-1,k];32 readln(x,y);33 writeln(calc(y+1)-calc(x));34 end;35 begin36 main;37 end.
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。