求救
查看原帖
求救
690561
违规用户名690561楼主2023/8/12 17:50
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
//#pragma G++ optimize(2)
//#pragma G++ optimize(3, "Ofast", "inline")
using namespace std;
int n, m, a[1000], dp[1000][10000], cnt;
int dfs(int x, int y, bool z1, bool z2){
	if(!z1 && !z2 && dp[x][y] != -1){
		return dp[x][y];
	}
	if(x > cnt){
		return 1;
	}
	int mx = 9;
	if(z2){
		mx = a[x];
	}
	int ans = 0;
	for(int i = 0;i <= mx;i++){
		if(abs(i - y) >= 2 || z1){
			ans += dfs(x + 1, i, z1 & (i == 0), z2 & (i == a[x]));
		}
	}
	return dp[x][y] = ans;
}
int solve(int x){
	memset(dp, -1, sizeof(dp));
	cnt = 0;
	while(x){
		a[++cnt] = x % 10;
		x /= 10;
	}
	return dfs(1, 0, true, true);
}
int main() {
	scanf("%d %d", &n, &m);
	printf("%d", solve(m) - solve(n - 1));
	return 0;
}
2023/8/12 17:50
加载中...