数位dp
引入
数位 ：是指把一个数字按位数一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 0~9，其他进制可类比十进制，就比如 链接: [SCOI2009] windy 数的二进制同理。
常见特征
- 要求统计满足一定条件的数的数量（即，最终目的为计数）；
- 这些条件经过转化后可以使用「数位」的思想去理解和判断；
- 输入会提供一个数字区间（有时也只提供上界）来作为统计的限制；
- 上界很大（比如 1018），暴力枚举验证会超时。
数位dp基本原理
主要有 记忆化搜索 和 循环迭代方式
数位dp有个通用的套路，就是先采用前缀和思想，将求解"[l, r]这个区间内的满足约束的数的数量”，转化为“[1,r]满足约束的数量区间[1,l-1]满足约束的数量。
- 考虑人类计数的方式，最朴素的计数就是从小到大开始依次加一。但我们发现对于位数比较多的数，这样的过程中有许多重复的部分。 例如，从
7000 数到 7999、从 8000 数到 8999、和从 9000 数到 9999 的过程非常相似，它们都是后三位从 000 变到
999，不一样的地方只有千位这一位，所以我们可以把这些过程归并起来，将这些过程中产生的计数答案也都存在一个通用的数组里。此数组根据题目具体要求设置状态，用递推或 DP 的方式进行状态转移。
例题： [SCOI2009] windy 数（这是我做的第一个数位dp的题目）
题目大意：给定一个区间 [l,r]，求其中满足条件 不含前导 0 且相邻两个数字相差至少为 2 的数字个数。
题目思路 （就是嘎嘎的模版）
数位dp-般解决的是一类数字问题:从到r有多少个数符合某个性质，其中和r都是很大的数,从l循环到r显然会TLE。
我们用f[i][j]表示搜到第i位，上一位数是j的情况下的方案总数。
这道题我们可以处理1一(l-1 )的方案数sum[l一1]和1-r的方案数sum[r],则$$ans=sum[r]-
sum[l-1]$$
接下来考虑怎么写转移
我们可以枚举每位上的0一9
特别地，如果前面的数取了能取的最大值或前面没有数字，那么这位上只能取到这位的最大数字
可能比较抽象，举个例子 654321
\[654???
\]
这时候第四位只能取到8，无法取到9 654321
\[654???
\]
第3位没有取到最大值，所以第4可以取到9,最后我们考虑限制条件:相邻两位绝对值大于等于2,如果前一-位是前导0，那么我们不需要考虑这位与0的绝对值，就是说0和1也是可以取到的,所以我们可以在处理下一位时把这位当做-2处理
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll windy[60];
ll dp[30][20];
ll dfs(ll pos,ll pre,bool flag,bool lead){
ll max_num;
if(pos==0)return 1;
if(!flag&&pre>0&&dp[pos][pre]!=-1)return dp[pos][pre];
if(flag)max_num=windy[pos];
else max_num=9;
ll res=0;
for(ll i=0;i<=max_num;i++)
if(abs(i-pre)>=2||lead)
res+=dfs(pos-1,i,flag&&(i==max_num),lead&&(i==0));
if(!flag)dp[pos][pre]=res;
return res;
}
ll solve(ll x){
int pos=0;
while(x){
windy[++pos]=x%10;
x/=10;
}
return dfs(pos,-2,1,1);
}
ll a,b;
int main() {
memset(windy, 0, sizeof(windy));
memset(dp, -1, sizeof(dp));
while(cin>>a>>b){
cout<<solve(b)-solve(a-1);
}
return 0;
}
参考来源： Oi-wiki