HDU2089 不要62

题解

有视频，直接看视频吧

数位dp入门视频+HDU2089

代码：

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const ll maxn = 1e6+10;
double eps = 1e-8;

int N,M;
int dp[maxn][2];
int nums[10];

int dfs(int pos,bool limit,bool pre_is6){
    if(!limit && dp[pos][pre_is6] != -1) return dp[pos][pre_is6];
    if(pos == 0) return 1;
    int up = limit? nums[pos]:9;
    int sum = 0;
    for(int i = 0;i<=up;i++){
        if(i == 4) continue;
        if(i == 2 && pre_is6) continue;
        sum += dfs(pos-1,limit && i == nums[pos],i == 6);
    }
    if(!limit) dp[pos][pre_is6] = sum;
    return sum;
}

int solve(int x){
    int pos = 0;
    while(x){
        nums[++pos] = x%10;
        x/=10;
    }
    return dfs(pos,1,0);
}

int main(){
    ios;
    memset(dp,-1, sizeof(dp));
    while(cin>>N>>M){
        if(N == 0 && M == 0) break;
        cout<<solve(M)-solve(N-1)<<endl;
    }
    return 0;
}