本題是很經典的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的技巧
zhoudaniel02@gmail.com
(周孝倫)
學校
:
銘傳大學
編號 : 235507
來源 : [223.140.157.105]
最後登入時間 ：
2024-04-29 21:31:07
Update
https://mousecoding.blogspot.com/2023/07/zerojudge-c543.html
我用的dp是dp[i][j] i是長度,j是開頭,dp定義是j開頭，長度為i的階梯數
代碼我自己試過了 最嚴苛的側資(100001個9有五個)花2.8118614016秒，但第三個任務TLE
下面是我的代碼
import java.util.*;
import java.math.BigInteger;
public class c543 {
public static void main(String []args) {
Scanner sc=new Scanner(System.in);
BigInteger[][] dp = new BigInteger[100001][11];
for (int i = 0; i < 100001; i++)
dp[i][9] = BigInteger.ONE;
for (int j = 1; j < 10; j++)
dp[0][j] = BigInteger.ONE;
dp[0][0]=BigInteger.ZERO;
for (int j = 8; j >= 0; j--)
for (int i = 1; i < 100001; i++) {
dp[i][j] = dp[i - 1][j].add(dp[i][j + 1]);
}
int time=0;
while (sc.hasNextLine()&&time!=5) {
time++;
String n=new BigInteger(sc.next()).add(BigInteger.ONE).toString();
BigInteger sum=BigInteger.ZERO;
for (int i = 0; i < n.length(); i++) {
for (int j=i==0?0:n.toCharArray()[i - 1]-'0'; j < n.toCharArray()[i]-'0'; j++)
sum = sum.add(dp[n.length() - i - 1][j]);
if (!(i == n.length() - 1 || n.toCharArray()[i] <= n.toCharArray()[i + 1]))
break;
}
System.out.println(sum);
}
}
}