P4124 [CQOI2016] 手机号码（数位dp

#include
using namespace std;
using VI = vector<int>;
using ll = long long;
ll dp[20][11][11][2][2][2];
int d[20];
ll dfs(int pos , int p1 , int p2 , int l3 , int is4 , int is8 , int limit){
 
    if(is4 && is8)return 0;
 
    if(pos == 0){
        if(l3)return 1;
        else return 0;
    }
    auto &x = dp[pos][p1][p2][l3][is4][is8];
    if(x != -1 && !limit) return x;
    ll res = 0 ;
    int up = (limit) ? d[pos] : 9;
    for(int i = 0 || pos == 11 ; i <= up ; i++){
        //防止最高位从 0 开始
        res += dfs(pos - 1 , i , p1 , l3 || (i == p2 && i == p1) ,is4 || i == 4 , is8 || i == 8 , limit && i == up);
    }
 
    if(!limit) x = res;
    return res;
 
}
ll work(ll x){
    int idx = 0;
    while(x){
        d[++idx] = x % 10;
        x /= 10;
    }
    if(idx != 11) return 0;
    return dfs(idx , 10 , 10 , 0 , 0 , 0 , 1);
    //memset(dp , -1 , sizeof dp);
}
 
 
int main(){
    memset(dp , -1 , sizeof dp);
    ll l,r;
    cin>>l>>r;
    cout<<work(r) - work(l-1);
}

不同的数的dp状态其实只有那个limit不同，把limit放在状态外就能实现一次memset

这题具体的就是要记录两位数字，其他的就和一般数位差不多