链接: https://www.luogu.com.cn/problem/P2657
记忆化搜索
其实不记忆化搜索也能过,直接搜...
#include<bits/stdc++.h> #define ll long long using namespace std; int a[10], f[16][2][10]; ll dfs(int pos, int lit, int begin, int last){ if(pos == 0) return 1; if(!lit && f[pos][begin][last] != 0) return f[pos][begin][last]; int high = lit ? a[pos] : 9; int ret = 0; for(int i = 0; i <= high; i++){ if(!begin || abs(last - i) > 1) ret += dfs(pos - 1, lit && i == high, begin || (i != 0), i); } if(!lit) f[pos][begin][last] = ret; return ret; } ll work(int n){ int cnt = 1; while(n > 0){ a[cnt++] = n % 10; n/=10; } return dfs(cnt - 1, 1, 0, -2); } int main(){ int n,m; cin>>n>>m; if(n > m) swap(n,m); printf("%lld", work(m) - work(n - 1)); }