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

代码:

SCOI2009windy数
 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.      
View Code

 

SCOI2009windy数,布布扣,bubuko.com

SCOI2009windy数

上一篇:Designing Evolvable Web API with ASP.NET 随便读,随便记 “The Internet,the World Wide Web,and HTTP”——HTTP


下一篇:搭建自己的服务器