zhoudaniel02@gmail.com
(周孝倫)
學校
:
銘傳大學
編號 : 235507
來源 : [223.140.157.105]
最後登入時間 ：
2024-04-29 21:31:07
我遇到TLE了
我弄了個dp[i][j]，代表j*10^i到(j+1)*10^i-1之間的階梯數，基本情況是j=9的話dp[i][j]=1(開頭為9的只有一個階梯數就是9999999....)，i=0時dp[i][j]=1(個位數像是7*10^0，7到(7+1)*10^0只有一個階梯數就是7，dp[0][0]=0(0不是階梯數)
因此 j 會在0到9之間，i則是依照題意在0到100000
一開始就先用一個大大的dp array[100001][10]
剩下的就是dp[i][j]=dp[i+1][j]+dp[i][j-1] (0<=j<=9) (1<=i<=100000)
最後再輸入數值，假設輸入了1267895
那答案就是dp[6][0]+dp[5][1]+dp[4][2]+dp[4][3]+dp[4][4]+dp[4][5]+dp[3][6]+dp[2][7]+dp[1][8]+dp[0][9] (6位數從0加到1-1,5位數從1加到2-1，4位數從2加到6-1...直到遇到比前一個數字小的
假設輸入1346215
dp[6][0]+dp[5][1]+dp[4][2]+dp[4][3]+dp[4][4]+dp[4][5]+dp[3][6]+dp[2][7]+dp[1][8]+dp[0][9]
答案就是
dp[6][0]+dp[5][1]+dp[5][2]+dp[4][3]+dp[4][4]+dp[4][5]+dp[3][6]
我的代碼:
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]);
}
while (sc.hasNext()) {
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);
}
}
}