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的满足条件的字符串的个数

代码：

var i,j,k,x,y:longint;
    f:array[-1..15,-1..15] of longint;
function calc(x:longint):longint;
 var i,j,len:longint;
     st:string;
     a:array[0..15] of longint;
 begin
  if x=0 then exit(0);
  str(x,st);
  len:=length(st);
  calc:=0;
  for i:=1 to len do a[i]:=ord(st[len+1-i])-48;
  for i:=1 to len-1 do
   for j:=1 to 9 do
    inc(calc,f[i,j]);
  for i:=1 to a[len]-1 do
    inc(calc,f[len,i]);
  for i:=len-1 downto 1 do
   begin
    for j:=0 to a[i]-1 do
     if abs(a[i+1]-j)>=2 then inc(calc,f[i,j]);
    if abs(a[i+1]-a[i])<2 then break;
   end;
 end;
procedure main;
 begin
   for i:=0 to 9 do f[1,i]:=1;
   for i:=2 to 10 do
    for j:=0 to 9 do
     for k:=0 to 9 do
      if abs(j-k)>=2 then f[i,j]:=f[i,j]+f[i-1,k];
   readln(x,y);
   writeln(calc(y+1)-calc(x));
 end;
begin
 main;
 end.