数位dp前置技能：记忆化搜索+动态规划
数位dp一般应用于：求出给定区间[A, B]内，符合条件P(x)的数x的个数。条件P(x)一般于数的大小无关，而与数的组成有关。
例题：求区间[a, b]中不包含49的数的个数,其中0<=a, b<=2e9。
我们要求区间[a, b]中不包含49的数的个数，注意到a, b的范围太大，暴力求解是肯定会超时的，因此要考虑动态规划，而如果直接记录下数字，又无法开出这么大的数组，因此我们引入数位dp。
要求区间[a, b]中不包含49的数的个数，很容易想到用前缀和的思想，即[a, b]=[0, b]-[0, a)，我们先求出给定a, b的每个位置的数，保存在数组s中，例如a=109，那么a[1]=9,a[2]=0,a[3]=1。然后开始dp，我们可以选择记忆化搜索或者是预处理+递推，记忆化搜索相对来讲较为容易一点。那么我们需要记录些什么呢？首先要记录长度，然后要记录当前的数位是否为4，这样就便于在记忆化搜索中得到的答案。
然后进行记忆化搜索，记录上一位是否为4并枚举这一位，如果没有限制就可以直接枚举，但是这样可能会超内存，因此我们每次都要判断是否有最大的限制。
参考代码：
#include <stdio.h>
#include <string.h>
using namespace std;
int a, b, digit[20], dp[20][2];
int dfs(int pos, bool if4, bool limit)
{
if (pos == 0)
return 1;/*如果一个数的数位从前到后遍历一遍没有continue,这个数符合条件，返回1*/
/*这里一般返回1，表示你枚举的这个数是合法的，那么这里就需要你在枚举时必须每一位都要满足题目条件，也就是说当前枚举到pos位，一定要保证前面已经枚举的数位是合法的。不过具体题目不同或者写法不同的话不一定要返回1 */
if (!limit && dp[pos][if4])
return dp[pos][if4];
/*为什么要返回呢？可以画图理解当我们搜到3XXX时，程序运行到1XXX时就已经把3XXX之后的搜索完了，记忆化也是这个用意*/
int cnt = 0;
int maxx = limit ? digit[pos] : 9;
/*求出最高可以枚举到哪个数字*/
for (int i = 0; i <= maxx; i++)
{
if (if4 && i == 9)
continue;
cnt += dfs(pos - 1, i == 4, limit && i == maxx);
/*只有之前有限制现在的达到了上限才能构成限制*/
}
return limit ? cnt : dp[pos][if4] = cnt;
/*如果没有限制,代表搜满了,可以记忆化,否则就不能*/
}
int solve(int x)
{
memset(digit, 0, sizeof(digit));
int pos = 0;
while (x)
{
digit[++pos] = x % 10;//计算每一位的数,放进digit数组;
x /= 10;
}
return dfs(pos, false, true);
}
int main()
{
scanf("%d%d", &a, &b);
printf("%d
", solve(b) - solve(a - 1));
return 0;
}
例题1：
HDU 3555 Bomb
Problem Description
The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence "49", the power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?
Input
The first line of input consists of an integer T (1 <= T <= 10000), indicating the number of test cases. For each test case, there will be an integer N (1 <= N <= 2^63-1) as the description.
The input terminates by end of file marker.
Output
For each test case, output an integer indicating the final points of the power.
Sample Input
3
1
50
500
Sample Output
0
1
15
Hint
From 1 to 500, the numbers that include the sub-sequence "49" are "49","149","249","349","449","490","491","492","493","494","495","496","497","498","499",so the answer is 15.
参考代码：
#include <stdio.h>
#include <string.h>
long long n, dp[20][2];
int digit[20];
long long dfs(int pos, bool if4, bool limit)
{
if (pos == 0)
return 1;
if (!limit && dp[pos][if4])
return dp[pos][if4];
long long cnt = 0;
int maxx = limit ? digit[pos] : 9;
for (int i = 0; i <= maxx; i++)
{
if (if4 && i == 9)
continue;
cnt += dfs(pos - 1, i == 4, limit && i == maxx);
}
return limit ? cnt : dp[pos][if4] = cnt;
}
long long solve(long long x)
{
memset(digit, 0, sizeof(digit));
int pos = 0;
while (x)
{
digit[++pos] = x % 10;
x /= 10;
}
return dfs(pos, false, true);
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
scanf("%lld", &n);
printf("%lld
", n + 1 - solve(n));
}
return 0;
}
例题2：
HDU 3652 B-number
Problem Description
A wqb-number, or B-number for short, is a non-negative integer whose decimal form contains the sub- string "13" and can be divided by 13. For example, 130 and 2613 are wqb-numbers, but 143 and 2639 are not. Your task is to calculate how many wqb-numbers from 1 to n for a given integer n.
Input
Process till EOF. In each line, there is one positive integer n(1 <= n <= 1000000000).
Output
Print each answer in a single line.
Sample Input
13
100
200
1000
Sample Output
1
1
2
2
参考代码：
#include <stdio.h>
#include <string.h>
long long n, dp[20][3][15];
/*dp[i][j][k]
i：数位
j：3种操作状况：0：末尾不是1；1：末尾是1；2：含有13
k：余数*/
int digit[20];
long long dfs(int pos, int pre, int mod, bool limit)
{
if (pos <= 0)
return pre == 2 && mod == 0;
if (!limit && dp[pos][pre][mod] != -1)
return dp[pos][pre][mod];
long long cnt = 0;
int maxx = limit ? digit[pos] : 9;
for (int i = 0; i <= maxx; i++)
{
if (pre == 2 || (pre == 1 && i == 3))
cnt += dfs(pos - 1, 2, (mod * 10 + i) % 13, limit && i == maxx);
else if (i == 1)
cnt += dfs(pos - 1, 1, (mod * 10 + i) % 13, limit && i == maxx);
else
cnt += dfs(pos - 1, 0, (mod * 10 + i) % 13, limit && i == maxx);
/*(mod * 10 + i) % 13这一步就是模拟除法过程，看能否整除13*/
/*根据pre判断三种操作状况，如果这一位是1，则把pre标为1，如果pre是2或者上一位是1且这一位是3，则把pre标为2，如果都不是，则把pre标为0*/
/*pre=2表示这个数位里包含了13，pre=1表示这个数位没包含13但是上一位是1，pre=0表示这个数位既不包含13，上一位也不是1*/
}
return limit ? cnt : dp[pos][pre][mod] = cnt;
}
long long solve(long long x)
{
memset(digit, 0, sizeof(digit));
int pos = 0;
while (x)
{
digit[++pos] = x % 10;
x /= 10;
}
return dfs(pos, 0, 0, 1);
}
int main()
{
while (~scanf("%lld", &n))
{
memset(dp, -1, sizeof(dp));
printf("%lld
", solve(n));
}
return 0;
}