终于明白数位DP是什么了
虽然说是dp，实际上是记忆化搜索
看这道题的题面：
不含前导零，且相邻两个数字之差至少为2的正整数被称为windy数。
求：在A和B之间，包括A和B，总共有多少个windy数？
这道题中给出了几个限定条件。
其中，前导零、数字上限(A,B)是数位dp的题目中比较常见的。
而“相邻数字之差至少为2”则是这道题特有的限定条件。
考虑用记忆化搜索来解决这道题。
首先考虑普通的搜索。搜索两次，边界分别设为给定的两个数，那么（solve[b] - solve[A-1])即为答案。
假设已经处理出了边界条件，共有n个数位，且从小到大第i位上的数字是num[i]。
那么，搜索时需要传递哪些变量？
int dfs(int cur,int las,bool start,bool lim) {
if(!cur) return 1;
if(f[cur][las] && !start && !lim) return f[cur][las];
int ans = 0;
for(int i = 0; i <= (lim?num[cur]:9); i++) {
if(!start && abs(i-las)<2) continue;
ans += dfs(cur-1,i,(start && !i),(lim && i==num[cur]));
}
if(!start && !lim) f[cur][las] = ans;
return ans;
}
cur表示当前是第几位（初始为n）
- 当cur减为0时，返回1
las表示上一位的数
start表示之前的所有数位是否为前导零
- 如果是前导零，则对后面的数位不造成影响（即使差值不大于2也可以）
- 当且仅当上一位是前导零（start为true），且这一位是0时，start为true
- start初始为true
lim表示之前的所有数位是否达到边界
- 如果到达边界，则枚举这一位时只枚举到这一位的实际大小。比如，数字为1234，前两位恰为12时，第三位只能枚举0~3，否则枚举0~9
- 当且仅当上一位到达边界（lim为true），且这一位的数字和实际数字相同时，lim为true。
- lim初始为true
普通的dfs完成了，考虑记忆化搜索。
需要解决的问题是：什么样的答案是可以记下来的？
能够直接调用的答案必须是有普遍性的。
可以想到，如果确定了当前位数和上一位位数，答案就是固定的。
不过，这也存在特殊情况。如果start或者lim为true，容易举出反例。
那么，排除掉这两种情况，其余答案记录，即为正解。
代码如下
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<queue>
#define MogeKo qwq
using namespace std;
int A,B,n,f[20][20],num[20];
int dfs(int cur,int las,bool start,bool lim) {
if(!cur) return 1;
if(f[cur][las] && !start && !lim) return f[cur][las];
int ans = 0;
for(int i = 0; i <= (lim?num[cur]:9); i++) {
if(!start && abs(i-las)<2) continue;
ans += dfs(cur-1,i,(start && !i),(lim && i==num[cur]));
}
if(!start && !lim) f[cur][las] = ans;
return ans;
}
int solve(int x) {
memset(f,0,sizeof(f));
n = 0;
while(x) {
num[++n] = x%10;
x /= 10;
}
return dfs(n,0,1,1);
}
int main() {
scanf("%d%d",&A,&B);
printf("%d",solve(B)-solve(A-1));
return 0;
}
View Code