数位dp好难啊 干脆打表吧

首先上暴搜算法。

inline bool windy(int a) {
    int last = a % 10;
    a /= 10;
    while (a) {
        if (a % 10 - last < 2 && last - a % 10 < 2) return false;
        last = a % 10;
        a /= 10;
    }
    return true;
}
int ans = 0, a, b;
int main() {
    cin >> a >> b;
    for (register int i = a; i <= b; i++) if (windy(i)) ans++;
    cout << ans << endl;
    return 0;
}

显然这个算法除了很慢其他没有任何问题。
注意到此程序可以轻松应对 1e7 数量级数据，故仅需对于大块区间打表。

int main() {
    int ans;
    for (register int n = 0; n < 2000; n++) {
        ans = 0;
        for (register int i = 1000000 * n; i <= 1000000 * (n + 1); i++) {
            if (windy(i)) ans++;
        }
        cout << ans << ',';
    }
    return 0;
}

在本地运行，将输出复制。

#include<iostream>
using namespace std;
int a, b, ans = 0;
int t[2001] = {/* 显然这里应该是表 */};
bool windy(int a) { ... }
int main(){
    cin >> a >> b;
    for (register int i = a; i <= b;) {
        // 对于大块区间直接使用预计算结果
        if (i % 1000000 == 0 && i + 1000000 < b){
            ans += t[i/1000000];
            i += 1000000;
        } else {
            if (windy(i)) ans++;    
            i++;
        }
    }
    cout << ans << endl;
    return 0;
}

数位 dp 模板题，显然数位 dp 我是只会记忆化搜索的。

#include<bits/stdc++.h>
using namespace std;
const int N=20;
const int B=10;
int a[N],f[N][N];
int dfs(int pos,int last,int lead,int limit){
	if(!pos)return 1;
	if(!lead&&!limit&&~f[pos][last])return f[pos][last];
	int res=0,up=limit?a[pos]:(B-1);
	for(int i=0;i<=up;i++){
		if(lead&&!i)res+=dfs(pos-1,0,lead&&!i,limit&&i==up);
		else if(lead||abs(i-last)>=2)res+=dfs(pos-1,i,lead&&!i,limit&&i==up);
	}
	if(!lead&&!limit)f[pos][last]=res;
	return res;
}
int calc(int x){
	int cnt=0;
	while(x){
		a[++cnt]=x%B;
		x/=B;
	}
	return dfs(cnt,0,1,1);
}
int main(){
	memset(f,-1,sizeof(f));
	int l,r;scanf("%d%d",&l,&r);
	printf("%d",calc(r)-calc(l-1));
	return 0;
}