BZOJ

BZOJ 1026

传送门

数位DP 一脸懵逼


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.