AcWing 1082. 数字游戏(java)
原题链接
中等
作者:
pen999
,
2020-07-30 17:47:08
,
所有人可见
,
阅读 470
import java.io.*;
import java.util.*;
public class Main {
private static int[][] dp;
public static void main(String[] args) throws IOException {
Scanner br = new Scanner(System.in);
while (br.hasNext()) {
int l = Integer.parseInt(br.next());
int r = Integer.parseInt(br.next());
dp = new int[15][10];
for (int i = 0; i < 10; i++) {
dp[1][i] = 1;
}
for (int i = 2; i < 15; i++) {
for (int j = 0; j < 10; j++) {
for (int k = j; k <= 9; k++) {
dp[i][j] += dp[i - 1][k];
}
}
}
System.out.println(count(r) - count(l - 1));
}
}
private static int count(int x) {
if (x == 0)
return 1;
List<Integer> list = new ArrayList<>();
while (x > 0) {
list.add(x % 10);
x /= 10;
}
int ans = 0;
int last = 0;
for (int i = list.size() - 1; i >= 0; i--) {
int t = list.get(i);
for (int j = last; j < t; j++) {
ans += dp[i + 1][j];
}
if (t < last)
break;
last = t;
if (i == 0)
ans++;
}
return ans;
}
}