AcWing 1083. Windy数
原题链接
中等
作者:
dannywang
,
2021-05-07 11:25:04
,
所有人可见
,
阅读 254
import java.util.*;
public class Main{
static int l, r;
static int[][] f = new int[10][11]; // f[i][j]表示以i开头的、长度为j的、相邻数字之差至少为2的数字的个数
public static int dp(int n){
if(n == 0) return 0;
List<Integer> nums = new ArrayList<>();
while(n > 0){
nums.add(n % 10);
n /= 10;
}
int res = 0, last = -2;
for(int i = nums.size() - 1; i >= 0; i --){
int x = nums.get(i);
if(x > 0){
for(int k = 0; k < x; k ++){
if(k == 0 && i == nums.size() - 1) continue;
if(Math.abs(k - last) >= 2)
res += f[k][i + 1];
}
}
if(Math.abs(x - last) >= 2) last = x;
else break;
if(i == 0) res ++;
}
// 特殊处理有前导0的数
// 一开始,有困惑:为什么第二层for循环不从0开始?
// 解释:诸如00040xxx等数被包含在f[4][5]之中了
for(int len = 1; len < nums.size(); len ++)
for(int j = 1; j <= 9; j ++)
res += f[j][len];
return res;
}
public static void init(){
// 初始化
for(int i = 0; i <= 9; i ++) f[i][1] = 1;
// 状态计算
for(int len = 2; len <= 10; len ++)
for(int i = 0; i <= 9; i ++)
for(int k = 0; k <= 9; k ++)
if(Math.abs(i - k) >= 2)
f[i][len] += f[k][len - 1];
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
l = sc.nextInt();
r = sc.nextInt();
init();
System.out.println(dp(r) - dp(l - 1));
}
}