第二届全国大学生算法设计与编程挑战赛B题：数位dp-dp_小x对数位dp很感兴趣,现在他在解决一道题目,要求求解出[x,y][x,y]闭区间内所有满

Description

小 x 对数位 dp 很感兴趣，现在他在解决一道题目，要求求解出[x,y]闭区间内所有满足以下性质的数字个数：

1. 相邻位数字差值的绝对值不能超过 7。
2. 且最低位与最高位差值的绝对值要大于 2。
   现在，给出 x=13930，y=457439。请你告诉小 x，满足要求的数字个数。

思路分析

x和y都不是很大，直接暴力搜索就行。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int solve(int x) {
	int a[6];
	int ind = 0;
	while(x) {
		int j = x % 10;
		x /= 10;
		a[ind++] = j;
	}
	if(abs(a[ind - 1] - a[0]) <= 2) {
		return 0;
	}
	for(int i = 1; i < ind; i++) {
		if(abs(a[i] - a[i - 1]) > 7) {
			return 0;
		}
	}
	return 1;
}

int main() {
	int res = 0;
	for(int i = 13930; i <= 457439; i++) {
		if(solve(i)) {
			res++;
		}
	}
	cout << res;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33