前言
上学期差不多整个学期都在打各种比赛，几乎没学新算法，因此寒假好好补一波算法，不过数位DP入个门也花了我两天，学习效率还没回来… …
模板题
给定一个数字区间[l,r]，问你区间内有多少数不含4，也不含连续的62。
题目范围是1e7，可以On预处理+前缀和O1查询，代码就不放了。
数位DP
今天的重点是数位DP。
数位DP的好处在于直接对位进行暴力，另外加上记忆化，可以大大减少时间。例如枚举千位时，一次枚举就相当于暴力下的一千次枚举。
初学数位DP，我感觉他的本质就是记忆化搜索。因此先上无记忆化的搜索代码：
#include <bits/stdc++.h>
using namespace std;
int a[20], pos;
int dfs(int pos, int sta, int lim) //枚举到第pos位，上一位是否是6，该位是否有约束
{
if (!pos)
return 1;
int sum = 0, up = lim ? a[pos] : 9;
for (int i = 0; i <= up; i++)
{
if (sta && i == 2)
continue;
if (i == 4)
continue;
sum += dfs(pos - 1, i == 6, lim && i == up);
}
return sum;
}
int solve(int mx)
{
pos = 0;
while (mx)
{
a[++pos] = mx % 10;
mx /= 10;
}
return dfs(pos, 0, 1);
}
int main()
{
int l, r;
while (cin >> l >> r && l + r)
cout << solve(r) - solve(l - 1) << endl;
return 0;
}
上面这份代码的写法其实比较奇怪，算是半个数位DP的写法吧。其中的lim是数位dp中一个关键点，可以看底下的参考博客理解。
这份代码本质上就是暴力，如果查询次数多或者数据范围加到1e9以上肯定是会TLE的，但是加上记忆化就不一样了，记忆化可以剪掉一大部分递归栈。记忆化只多了四五行代码：
/*
* @Author: hesorchen
* @Date: 2020-12-30 16:53:18
* @LastEditTime: 2021-01-12 21:17:10
* @Description: 栽种绝处的花
*/
#include <bits/stdc++.h>
using namespace std;
int a[20], pos;
int dp[20][2];
int dfs(int pos, int sta, int lim) //枚举到第pos位，上一位是否是6，该位是否有约束
{
if (!pos)
return 1;
if (!lim && dp[pos][sta] != -1) //记忆化
return dp[pos][sta];
int sum = 0, up = lim ? a[pos] : 9;
for (int i = 0; i <= up; i++)
{
if (sta && i == 2)
continue;
if (i == 4)
continue;
sum += dfs(pos - 1, i == 6, lim && i == up);
}
if (!lim) //记忆化
dp[pos][sta] = sum;
return sum;
}
int solve(int mx)
{
memset(dp, -1, sizeof dp);
pos = 0;
while (mx)
{
a[++pos] = mx % 10;
mx /= 10;
}
return dfs(pos, 0, 1);
}
int main()
{
int l, r;
while (cin >> l >> r && l + r)
cout << solve(r) - solve(l - 1) << endl;
return 0;
}
这里的记忆化需要判断!limit，这是一个稍难的点，事实上，就是为了避免limit或者非limit两种状态的冲突，经过实测，我们完全可以记忆化中的一种，不过就此题来说，显然!limit的状态更多，因此选择记忆这种效率更高。具体理解看底下的参考博客吧。