bzoj 1026 DP，数位统计

2013-11-20 08:11

原题传送门http://www.lydsy.com/JudgeOnline/problem.php?id=1026

首先我们用w[i,j]表示最高位是第i位，且是j的windy数个数

那么我们可以写出转移

w[i,j]:=w[i-1,k] abs(k-j)>=2

首先对于询问的a,b区间，我们可以转化成求1-a的个数，1-b的个数，然后差就行了

那么我们要求的就是1-x之间的windy数

假设x一共有len位，那么我们求len-1位以下的windy数可以直接用w算出来，直接

累加w[i,j]就行了

那么我们对于len位的数，只需要改变枚举的上界就好了，相当于固定第i位，求第i+1位的

情况，然后特判下如果abs(c[i]-c[i+1])<2（c[i]为x的第i位）直接退出就行了

 1 /**************************************************************
 2     Problem: 1026
 3     User: BLADEVIL
 4     Language: Pascal
 5     Result: Accepted
 6     Time:0 ms
 7     Memory:228 kb
 8 ****************************************************************/
 9  
10 //By BLADEVIL
11 var
12     w                   :array[0..10,-1..10] of longint;
13     c                   :array[0..10] of longint;
14     a, b                :longint;
15      
16 function ask(x:longint):longint;
17 var
18     len, Sum, i, j      :longint;
19      
20 begin
21     if x=0 then exit(0);
22     len:=0;
23     while x>0 do
24     begin
25         inc(len);
26         c[len]:=x mod 10;
27         x:=x div 10;
28     end;
29     ask:=0;
30     for i:=1 to len-1 do
31         for j:=1 to 9 do
32             ask:=ask+w[i,j];
33              
34     for j:=1 to c[len]-1 do
35         ask:=ask+w[len,j];
36          
37     for i:=len-1 downto 1 do
38     begin
39         for j:=0 to c[i]-1 do
40             if abs(c[i+1]-j)>=2 then ask:=ask+w[i,j];
41         if abs(c[i+1]-c[i])<2 then break;
42     end;
43 end;
44  
45 procedure main;
46 var
47     i, j, k             :longint;
48      
49 begin
50     for i:=0 to 9 do w[1,i]:=1;
51     for i:=2 to 10 do
52         for j:=0 to 9 do
53             for k:=0 to 9 do
54                 if abs(j-k)>=2 then w[i,j]:=w[i,j]+w[i-1,k];
55     readln(a,b);
56     writeln(ask(b+1)-ask(a));
57 end;
58  
59 begin
60     main;
61 end.