数位dp

有关数字每一位的性质的计数问题

题目

不要62

题意

  • 给定一个区间[n, m],求在区间内的数字中不包含62(6和2需要连在一起)和4的数字的个数

题解

  • 状态设计:dp[i][j],长度为i的数字,最高位为j的符合条件的数字的个数。
  • 状态转移方程:
    j \(\neq\) 4时:
    dp[i][j] = \(\sum_{k=0}^9 dp[i-1][k](j\neq6 || k\neq2)\)
  • 边界:dp[0][0] = 1;
  • 结果:扫一遍需要取到的dp[i][j],求和.

思路的博客:
不要62

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
int dp[9][10];
int bits[8];
void init(){
dp[0][0] = 1;
for(int i=1; i<=8; i++){
for(int j=0; j<=9; j++)
for(int k=0; k<=9; k++){
if(j != 4 && !(j==6&&k==2)){
dp[i][j] += dp[i-1][k];
}
}
}
}
int n, m;
int solve(int n){
int len = 1;
while(n){
bits[len++] = n%10;
n /= 10;
}
bits[len] = 0;
int ans = 0;
for(int i=len-1; i>=1; i--){
for(int j=0; j<bits[i]; j++){
if( j!=4 &&!(bits[i+1] ==6&&j ==2))
ans += dp[i][j];
}
if(bits[i] == 4||(bits[i+1] == 6&&bits[i] == 2))
break;
}
return ans;
}
int main()
{
init();
while(~scanf("%d%d", &n, &m)&&n+m!=0){
//为什么是+1,看递推的过程!表示小于的数字
printf("%d\n", solve(m+1)-solve(n));
}
return 0;
}

递归的写法:

未解决的问题

文章目录
  1. 1. 题目
    1. 1.1. 题意
    2. 1.2. 题解
    3. 1.3. AC代码
  2. 2. 未解决的问题
{{ live2d() }}