#C241121A. [SCOI2009] windy 数

标签（Label）

动态规划
数位dp

网址（Website）

P2657 [SCOI2009] windy 数 - 洛谷

题目（Problem）

题目背景

windy 定义了一种 windy 数。

题目描述

不含前导零且相邻两个数字之差至少为 $2$ 的正整数被称为 windy 数。windy 想知道，在 $a$ 和 $b$ 之间，包括 $a$ 和 $b$ ，总共有多少个 windy 数？

输入格式

输入只有一行两个整数，分别表示 $a$ 和 $b$。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

1 10

样例输出 #1

样例 #2

样例输入 #2

25 50

样例输出 #2

提示

数据规模与约定：

对于全部的测试点，保证 $1 \leq a \leq b \leq 2 \times 10^9$。

题解（Solution）

想起来没什么难度，直接打一个记忆化搜索就好了，就是考虑的东西有点多。

最开始的处理肯定是把这个两个数字转换成数组来存储，由于考虑到大的数位对小的会有影响，因此选择倒叙存储，让 $a_1$ 存最大的数位。我们定义题目中的 $a$ 转化出来为 $L_i$ ，$b$ 转化出来是 $R_i$ 。

然后就开始 $\text{dp}$ 。发现如果进入的数位在 $(L_i,R_i)$ 范围内，那么后面的数字只需要满足“ 不含前导零且相邻两个数字之差至少为 $2$ ”这一个条件，直接往下搜就行了，这样往后走就没有其他限制；如果当前枚举的数位与 $L_i$ 或者 $R_i$ 相等，只有前面一直有大小限制的情况下当前枚举的数位才会受到限制，即前面枚举的数位必须和 $a$ 或 $b$ 的前面的数位都相等才有限制。除了这些，还有一个点就是“不含前导零”的条件，可以记录前面有没有数不为零，到这一位的时候判断即可。

综上，记录 $5$ 个值：当前位数 $x$ ，上一位 $j$ ，前面的数位是否和 $a$ 相等 $xl$ ，前面的数位是否和 $b$ 相等 $xr$ ，前面有没有数不为零 $hav$ 。知道这些之后，代码就非常好阅读了。

时间复杂度： $\le O(A)$ 。$A$ 表示值域，由于记忆化搜索，所以其实很快。

代码（Code）

100分

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
#define show(a,b) {For(i,1,n) cerr<<a[i]<<b;cerr<<'\n';}
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
#define in(x,l,r) (l<=x && x<=r)
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}template<typename G>
void write(G x){
	if(x<0) putchar('-'),write(-x);
	else if(x<=9) putchar(x+'0');
	else write(x/10), putchar(x%10+'0');
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 16;
const int S = 2e9+5;
bool ST;
int L[N],R[N],ans,st=1;
int f[N][N][2][2][2];

inline int dfs(int x,int j,bool xl,bool xr,bool hav){
	if(f[x][j][xl][xr][hav]) return f[x][j][xl][xr][hav];
	if(x==11) return 1;int res = 0;
	int l = xl ? L[x] : 0;
	int r = xr ? R[x] : 9;
	For(i,l,r) if(!hav || !in(i,j-1,j+1))
		res += dfs(x+1, i, xl&&i==l, xr&&i==r, hav||i);
	return f[x][j][xl][xr][hav] = res;
}

void Solve(){
	int l = rd(), r = rd();
	Rof(i,10,1) L[i]=l%10, l/=10;
	Rof(i,10,1) R[i]=r%10, r/=10;
	ans = dfs(1,12,1,1,0);
	write(ans), putchar('\n');
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = 1;double Tim = clock();
	while(T--) Solve();
	return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}