#27572: Digit DP


fire5386 (fffelix)

School : 國立清華大學
ID : 115822
IP address : [36.227.155.149]
Last Login :
2022-01-17 19:27:26
c543. 四、階梯數字(ladder) (APCS 加強題) -- 板橋高中模擬賽APCS | From: [111.243.21.75] | Post Date : 2021-10-16 10:29

本題是很經典的Digit DP

dp[100001][10][2]

我們把n反過來看

dp[i][j][k] - 長度為i, 最後一個數字為j, k:目前大於(1)或小於(0)n的數字有幾個

初始dp[0][9][0] = 1,因為要讓後面的遞減

我們可以用四層for loop來窮舉所有狀態

第一層窮舉 i 長度由小到大 (|n|:n的長度)

第二層窮舉最後一個加入的數字 j (10:0~9)

第三層窮舉大於或是小於 k (2:false, true)

第四層窮舉新加入的數字 add (10:0~9)

最後把所有的加起來就是答案了

參考程式碼

https://66lemon66.blogspot.com/2021/10/zerojudge-c543-ladder-apcs-c.html

額外練習:g352和g396都是運用digit dp的技巧

 
ZeroJudge Forum