SCOI2009windy数
2020-12-13 03:10
标签：style blog http color os art 数位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的满足条件的字符串的个数 代码： SCOI2009windy数,搜素材,soscw.com SCOI2009windy数 标签：style blog http color os art 原文地址：http://www.cnblogs.com/zyfzyf/p/3798128.html
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 do
14 for j:=1 to 9 do
15 inc(calc,f[i,j]);
16 for i:=1 to a[len]-1 do
17 inc(calc,f[len,i]);
18 for i:=len-1 downto 1 do
19 begin
20 for j:=0 to a[i]-1 do
21 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 begin
27 for i:=0 to 9 do f[1,i]:=1;
28 for i:=2 to 10 do
29 for j:=0 to 9 do
30 for k:=0 to 9 do
31 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 begin
36 main;
37 end.