好累啊啊啊~~~~~~，刷了一天的題了，嗯，再寫兩篇題解我就去頹Slay。。。

思路分析：

剛剛我們講了數位DP，現在就感受一下吧。（其實我也就只敢做做安徽的題，四川的數位DP想都不敢想）

嗯好，我們開始分析題目吧！

這題怎么說呢，額，——很暴力，嗯，非常暴力，暴力到我都不敢去想，（可以說它和大暴力只相差了一個苗條的YLK），然而它是能過的。

怎么個暴力法呢？

? ? ? ? ? ? ? ? ? ? ? ——直接暴力枚舉面積枚舉這個數各個數位相加的和，夠暴力吧！

開始設計狀態（然而我們寫的是dfs，其實是一樣的），dp[pos][p][sum]表示當前已經做到了pos位，模我們枚舉的各個數位的和的余數為p，當前各數位相加和為sum。

做dfs的時候只要當pos>len且p=0，sum=我們枚舉的各個數位之和，就代表這是一種合法的方案。

代碼實現：

vardp: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; varres:int64;i,limit:Longint; beginif pos>len thenif (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 dores:=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; beginlen:=0; part:=0;while x>0 dobegin inc(len); a[len]:=x mod 10; x:=x div 10; end;for oo:=1 to len*9 dobeginfillchar(dp,sizeof(dp),255);part:=part+dfs(1,0,0,1,1);end; end; beginread(l,r);ans:=ans-part(l-1)+part(r);writeln(ans); end.

轉載于:https://www.cnblogs.com/WR-Eternity/p/9931415.html

總結

以上是生活随笔為你收集整理的ANOI 2009 【同类分布】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。