不要62——数位dp打卡

不要62

简单的数位dp
思路：预处理加前缀和
特判两个条件就可以了

代码：

#include 
#include 
using namespace std;
const int N = 12;
int f[N][N];

void init(){
    for(int i = 0;i<=9;i++) if(i!=4) f[1][i] = 1;
    for(int i = 2;i<=N;i++){
        for(int j = 0;j<=9;j++){
            if(j==4) continue;
            for(int k = 0;k<=9;k++){
                if(k==4) continue;
                if(j==6&&k==2) continue;
                f[i][j] += f[i-1][k];
            }
        }
    }
}

int dp(int n){
    if(!n) return 1;
    vector<int> nums;
    while(n) nums.push_back(n%10),n/=10;
    int res = 0;
    int last = 0;
    for(int i = nums.size()-1;i>=0;i--){
        int x = nums[i];
        for(int j = 0;j<x;j++){
            if(j==4||(last==6&&j ==2))
                continue;
            res += f[i+1][j];
        }
        if(x == 4||(last==6&&x ==2)) break;
        last = x;
        if(!i) res++;
    }
    return res;

}
int main() {
    init();
    int n,m;
    while(cin>>n>>m,n||m){
        cout<<dp(m)-dp(n-1)<<endl;
    }
    return 0;
}

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
46
47
48
49