好累啊啊啊~~~~~~，刷了一天的题了，嗯，再写两篇题解我就去颓Slay。。。

思路分析：

刚刚我们讲了数位DP，现在就感受一下吧。（其实我也就只敢做做安徽的题，四川的数位DP想都不敢想）

嗯好，我们开始分析题目吧！

这题怎么说呢，额，——很暴力，嗯，非常暴力，暴力到我都不敢去想，（可以说它和大暴力只相差了一个苗条的YLK），然而它是能过的。

怎么个暴力法呢？

——直接暴力枚举面积枚举这个数各个数位相加的和，够暴力吧！

开始设计状态（然而我们写的是dfs，其实是一样的），dp[pos][p][sum]表示当前已经做到了pos位，模我们枚举的各个数位的和的余数为p，当前各数位相加和为sum。

做dfs的时候只要当pos>len且p=0，sum=我们枚举的各个数位之和，就代表这是一种合法的方案。

代码实现：

var

    dp:array[1..20,0..180,0..180] of int64;

    a:array[1..20] of Integer;

    i,len,oo:Longint;

    ans,l,r:int64;

function dfs(pos,p,sum,lead,flag:Longint):int64;

var

    res:int64;

    i,limit:Longint;

begin

    if pos>len then

        if (sum=oo)and(p=0) then exit(1) else exit(0);

    if sum>oo then exit(0);

    if (dp[pos][p][sum]<>-1)and(lead+flag=0) then exit(dp[pos][p][sum]);

    if flag=1 then limit:=a[len-pos+1] else limit:=9;

    res:=0;

    for i:=0 to limit do

        res:=res+dfs(pos+1,(p*10+i)mod oo,sum+i,ord((lead=1)and(i=0)),ord((flag=1)and(i=limit)));

    if lead+flag=0 then dp[pos][p][sum]:=res;

    dfs:=res;

end;

function part(x:int64):int64;

begin

    len:=0; part:=0;

    while x>0 do

        begin inc(len); a[len]:=x mod 10; x:=x div 10; end;

    for oo:=1 to len*9 do

    begin

        fillchar(dp,sizeof(dp),255);

        part:=part+dfs(1,0,0,1,1);

    end;

end;

begin

    read(l,r);

    ans:=ans-part(l-1)+part(r);

    writeln(ans);

end.

巴特西

ANOI 2009 【同类分布】

思路分析：

代码实现：

最新文章

热门文章