BZOJ 1026

传送门

Orz ZYK

数位DP过程中记录下上一位是啥,然后…不会了TAT 还是去戳上面那篇大爷的题解吧 = =


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
program bzoj_1026;
var d:array[1..10]of longint;
a,b:longint;
f:array[1..10,0..9,0..1]of longint;
function dfs(p,pre:longint;flag,lim:boolean):longint;
var limit,i:longint;
begin
if p<1 then exit(ord(flag));
if (not lim)and(f[p,pre,ord(flag)]<>-1) then exit(f[p,pre,ord(flag)]);
if lim then limit:=d[p] else limit:=9;
dfs:=0;
for i:=0 to limit do if (abs(i-pre)>=2)or(not flag) then inc(dfs,dfs(p-1,i,flag or (i<>0),lim and(i=limit)));
if not lim then f[p,pre,ord(flag)]:=dfs;
end;
function solve(x:longint):longint;
var len:longint;
begin
if x=0 then exit(0);
len:=0;
while x>0 do
begin
inc(len);
d[len]:=x mod 10;
x:=x div 10;
end;
fillchar(f,sizeof(f),255);
exit(dfs(len,0,false,true));
end;
begin
readln(a,b);
writeln(solve(b)-solve(a-1));
end.