\[I\]

平常的做法是設 \(f_{i,j}\) 為 \(0\)~\(j \times 10^{i-1}\) 的合法個數,這里用某種神奇而快速的做法。

簡化題意:

• 不要 \(6\ 2\) 連在一起的數字。
• 不要有 \(4\) 的數字。

我們暫且設 :

• \(f_{i,1}\) 為 \(0\)~\(10^i-1\) 的合法個數。
• \(f_{i,2}\) 為 \(0\)~\(10^i-1\) 的不合法個數。
• \(f_{i,3}\) 為 \(0\)~\(10^i-1\) 的開頭為 \(2\) 的合法個數。

我們考慮到要求 \(62\) 這種東西,所以要用 \(f_{i,3}\)。
其實這三個數組可以縮成一個,就是 \(f_{i,1}\)。

為了方便我們把 \(f_{i,3}\) 去掉。

考慮到 \(f_{i,3}\) 要求合法,且開頭是 \(2\)。所以我們用上一位合法的開頭加上一個 \(2\) 就是轉移。
\[f_{i,3}=f_{i-1,1}\]

考慮合法的如何轉移。因為 \(6\ 2\) 會導致不合法,而現在可以給開頭加上一個 \(6\),所以我們只需要減去一個上一位的開頭為 \(2\) 的個數。

\[f_{i,1}=-f_{i-2,1}\]

然后考慮到上一次合法的數字轉移過來只有開頭加上 \(4\) 會 \(GG\),所以加上一個 \(f_{i-1,1} \times 9\)。

\[f_{i,1}=f_{i-1,1} \times 9-f_{i-2,1}\]

然后考慮 \(f_{i,2}\) 的轉移。我上一位的不合法數字在開頭上面加上什么都是不合法的。且我可以給合法的數字加上一個 \(4\) 使其不合法。再且我可以給那些以 \(2\) 開頭的數字加上一個 \(6\) 使其不合法。所以就是:

\[f_{i,2}=f_{i-1,2} \times 10+f_{i-1,1}+f_{i-2,1}\]

預處理時間復雜度 \(O(k)\),\(k\) 為位數。

查詢就更簡單了~

首先我們要把上一位的不合法減掉:

\[ans-=num_i\times f_{i-1,2}\]

如果我的數字本身出現了不合法,那么我后面的所有數字都是不合法的。\(num_i\times f_{i-1,2}\) 已經減過了,就減 \(num_i \times f_{i-1,1}\)。

\[ans-=num_i \times f_{i-1,1}\]

如果數字本身沒有不合法,那么看情況討論。

• 如果出現 \(4\),那么上一位的所有合法都是廢的。

\[ans-=f_{i-1,1}\]

• 如果出現 \(6\),那么上一位所有 \(2\) 開頭的都是廢的。

\[ans-=f_{i-2,1}\]

• 如果我現在存在了一個 \(6\ 2\),那么這一位所有的 \(2\) 都是廢的。

\[ans-=f_{i-1,1}\]

最后統計一下數字本身是否合法。

varfuck:array[-1..15,-1..3] of longint;i,j,x,y:longint;function Slove(ans:longint):longint; varnum:array[-1..15] of longint;i,len,flag:longint;s:string; beginfillchar(num,sizeof(num),0); Delete(s,1,length(s));str(ans,s); len:=length(s); flag:=1;for i:=1 to len do val(s[i],num[len-i+1]);for i:=len downto 1 dobegindec(ans,num[i]*fuck[i-1,2]);if flag=666 then dec(ans,num[i]*fuck[i-1,1]) elsebeginif num[i]>4 then dec(ans,fuck[i-1,1]);if num[i]>6 then dec(ans,fuck[i-2,1]);if (num[i+1]=6)and(num[i]>2) then dec(ans,fuck[i-1,1]);end;if (num[i]=4)or((num[i+1]=6)and(num[i]=2)) then flag:=666;end;exit(ans); end;beginfuck[0,1]:=1;for i:=1 to 9 dobeginfuck[i,1]:=fuck[i-1,1]*9-fuck[i-2,1];fuck[i,2]:=fuck[i-1,2]*10+fuck[i-1,1]+fuck[i-2,1];end;read(x,y);while (x<>0)and(y<>0) dobeginwriteln(Slove(y+1)-Slove(x)); read(x,y);end; end.

\[II\]

同樣是遞推來做。

我們設 \(f_{i,j}\) 為 \((j-1) \times 10^{i-1}+1\)~\(j \times 10^{i-1}\) 的幸運數字的個數。跟平常一樣,是為了壓空間,也是為了好轉移。

轉移就異常的簡單了:(且滿足 \(x\ y\) 不是 \(6\ 2\),也不是 \(4\))

\[f_{i,x}=\sum\limits^{9}_{x=0} \sum\limits^{9}_{y=0} f_{i-1,y}\]

然后我們在查詢的時候直接加上就好了。

來談談一直沒有說過的查詢,其實隨便列舉一個數字 \(2333\):

• 最高位 : \(0\)~\(1000\),\(1001\)~\(2000\)
• 次高位 : \(0\)~\(100\),\(101\)~\(200\),\(201\)~\(300\)
• 第三高位 : \(0\)~\(10\),\(11\)~\(20\),\(21\)~\(30\)
• 最低位 : \(0\)~\(1\),\(1\)~\(2\),\(2\)~\(3\)

所以大概明白了數位 \(DP\) 的套路。

varfuck:array[-1..15,-1..10] of int64;i,x,y:longint;function Slove(x:longint):int64; varnum:array[-1..15] of longint;i,j,len:longint;s:string; beginfillchar(num,sizeof(num),0);str(x,s); len:=length(s); Slove:=0;for i:=1 to len do val(s[i],num[len-i+1]);for i:=len downto 1 dobeginfor j:=0 to num[i]-1 dobeginif (num[i+1]=6)and(j=2) then continue;inc(Slove,fuck[i,j]);end;if (num[i]=4) then break;if (num[i]=2)and(num[i+1]=6) then break;end; end;beginfor i:=0 to 9 do fuck[1,i]:=1; fuck[1,4]:=0;for i:=2 to 10 do for x:=0 to 9 do for y:=0 to 9 do begin if (x=6)and(y=2) then continue; if (x=4)or(y=4) then continue; inc(fuck[i,x],fuck[i-1,y]); end;read(x,y);while (x<>0)and(y<>0) dobeginwriteln(Slove(y+1)-Slove(x));read(x,y);end; end.

第一道數位 \(DP\)。

由于空間不夠,所以我們必須要壓縮一下。

所以我們設 \(f_{i,j}\) 為 \(1\)~\(X\) 的 \(windy\)。(其中 \(X\) 滿足第一位等于 \(j\),且有 \(i\) 位)

\[f_{i,j}=\sum\limits^{9}_{l=j+2} f_{i-1,l} +\sum\limits^{j-2}_{l=0} f_{i-1,l}\]

for i:=0 to 9 do fuck[1,i]:=1;for i:=2 to 20 do for j:=0 to 9 do begin for k:=j-2 downto 0 do inc(fuck[i,j],fuck[i-1,k]); for k:=j+2 to 9 do inc(fuck[i,j],fuck[i-1,k]); end;

這樣子就很好的壓縮了空間。

我們把 \(C(l,r)\) 變為 \(C(r+1)-C(l)\)

(\(C(r)-C(l-1)\) 莫名 \(WA\) 了?)

我們考慮求一個數字 \(x\) 的 \(windy\)。我們定義 \(X\) 為 \(x\) 倒立過來的數組,\(len\) 為數組長度。如 \(x=7192\),\(X_i=\{2,9,1,7\},len=4\)。

我們先把 \(0\)~\(999\) 的 \(windy\) 求一下。

\[\sum\limits^{len-1}_{i=1}\sum\limits^{9}_{j=1} f_{i,j}\]

for i:=1 to len-1 do for j:=1 to 9 do inc(Windy,fuck[i,j]);

然后把 \(1000\)~\(6999\) 的求了。

\[\sum\limits^{X_{len}-1}_{i=1} f_{len,i}\]

for i:=1 to num[len]-1 do inc(Windy,fuck[len,i]);

最后的最難搞~要把剩下的求了。

\[\sum\limits^{1}_{i=len-1} \sum\limits^{X_{i}-1}_{j=0} f_{i,j} (abs(j-X_{i+1})>=2)\]

for i:=len-1 downto 1 dobeginfor j:=0 to num[i]-1 do if abs(j-num[i+1])>=2 then inc(Windy,fuck[i,j]);if abs(num[i]-num[i+1])<2 then break;end;

就沒了。

轉載于:https://www.cnblogs.com/FibonacciHeap/articles/10321802.html

總結

以上是生活随笔為你收集整理的数位 DP 入门 (不要 62+windy 数)的全部內容，希望文章能夠幫你解決所遇到的問題。

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